I005 Formal Languages and Automata I

Languages and grammars. Chomsky hierarchy. & Finite automata and regular grammars. & Properties of regular languages. & Context-free grammars and pushdown automata. & Properties of context-free languages. & Deterministic pushdown automata. & Turing machines. Computable languages and functions. & Undecidability, (semi)decidability. Halting problem for TM. & Post's correspondence problem. Undecidable CFL problems.

Bibliography:

• M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978

• J. E. Hopcroft, J. D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, 1969

• J. E. Hopccroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979

• M. Chytil, Automaty a gramatiky, SNTL Praha, 1984