Context-free grammars find applications in computer science (for example, in interpreters and compilers) and in linguistics.

The course includes proofs of main classical mathematical results about context-free grammars and pushdown automata, including the complement and intersection theorems, the representation of languages by homomorphisms, the undecidability of the equivalence problem for grammars, and some other algorithmic problems.

Program

1. Formal languages.
2. Context-free grammars.
3. Dyck languages and Łukasiewicz languages.
4. Normal forms of context-free grammars.
5. The pumping lemma for context-free languages.
6. Pushdown automata. Characterization of context-free languages.
7. Closure properties for the class of context-free languages. The intersection of a context-free language with a regular language.
8. Homomorphisms and context-free languages.
9. The Chomsky-Schützenberger theorem.
10. Deterministic context-free languages.
11. Algorithmically decidable problems. Noncontracting grammars. The word problem. The emptiness problem. The infiniteness problem. The equivalence problem for finite automata. The equivalence problem for deterministic pushdown automata.
12. Algorithmically undecidable problems. The intersection of context-free languages. The complement of a context-free language. The regularity problem. Context-freeness problems.

Lecturer
Pentus Mati Reinovich

Financial support
The course is supported by the Ministry of Science and Higher Education of the Russian Federation (the grant to the Steklov International Mathematical Center, Agreement no.  075-15-2022-265).

Institutions
Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
Steklov International Mathematical Center