Charles Explorer logo

Automata and Grammars

Class at Faculty of Mathematics and Physics |


Word, language, operations on languages

Formal grammar, regular grammar, finite-state automaton, Nerode's Theorem, minimal automaton, non-determinism

Closure properties of the class of regular languages, regular expressions, Kleene's Theorem, Pumping Lemma for regular languages

Finite-state transducer, decision problems for regular languages

Context-free grammar, Chomsky normal form, Greibach normal form, closure properties of the class of context-free languages, Pumping Lemma for context-free languages

Pushdown automaton, CYK-algorithm, deterministic pushdown automaton, decision problems for context-free languages

Context-sensitive grammar, context-sensitive language, closure properties and decision problems, linear-bounded automaton

Turing machines, halting problem, reduction, undecidable problems, recursively enumerable language, Chomsky hierarchy, the universal language, the diagonal language.


Introductory lectures on Automata Theory and Formal Grammars. The emphasis is put on basic terminology and fundamental results.

We study and highlight connections between the following formal models: finite-state and push-down automata (both deterministic and non-deterministic), Turing machines (including the halting problem), regular, context-free, and context-sensitive grammars.