Syllabus
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.
Annotation
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.