Lecturer(s)


Kühr Tomáš, Mgr. Ph.D.

Vychodil Vilém, doc. RNDr. Ph.D.

Course content

Basic notions: formal language, hierarchy of grammars and languages. Finite automata: deterministic and nondeterministic finite automata, their extension, mutual relationship, and applications. Regular grammars and languages: relationship to finite automata, closure properties of regular languages, criteria of regularity, minimization of automata. Regular expressions and their applications: standard and extended regular expressions, application for text processing, selected topics. Contextfree languages: definition and properties, derivation trees, properties of contextfree languages and their relationship to regular languages Pushdown automata: variants, relationship to contextfree languages, topdown syntactic analysis, bottomup syntactic analysis, deterministic pushdown automata.

Learning activities and teaching methods

Laboratory Work
 Preparation for the Course Credit
 16 hours per semester
 Preparation for the Exam
 50 hours per semester

Learning outcomes

This is an introduction course to formal languages, grammars, and automata theory and their applications in computer science. The main emphasis is put on regular and contextfree languages. The course introduces essential background which is needed to study topics in further courses including computability theory, complexity analysis, algorithm design for text searching, compiler constructions, etc., which are relevant for computer science applications.
1. Knowledge Describe basic generative and analytical formalisms for languages.

Prerequisites

Basic notions of discrete and algorithmic mathematics (sets, relations).

Assessment methods and criteria

Oral exam, Written exam, Student performance
Credit: students have to pass a written test Exam: students have to pass a written and oral exam test

Recommended literature


Hopcroft J. E., Motwani R., Ullman J. D. (2006). Introduction to Automata Theory, Languages, and Computation. AddisonWesley, Boston.

Kozen D. C. (1997). Automata and Computability. Springer.

LAWSON M. V. (2003). Finite Automata. Chapman & Hall/CRC.

Melichar, B. (2003). Jazyky a překlady. Skriptum, přepracované 2. vydání. Vydavatelství ČVUT, Praha.

Simovici D. A., Tenney R. L. (1999). Theory of Formal Languages with ApplicationsM. Simon. World Scientific, Singapore.

Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
