The formal grammar theory lies at the intersection of mathematical logic, theoretical computer science, and linguistics. Formal grammars are used to describe both natural languages and computer languages (for example, programming languages).

The course explores two families of grammatical formalisms viz. Chomsky generative grammars and Lambek categorial grammars. Special attention is given to grammars for which efficient (polynomial-time) parsing algorithms exist, the latter making nontrivial use of the dynamic programming approach. Such grammars are of greatest interest for applications.

Syllabus:

1. Context-free grammars. Chomsky normal form. The Cocke–Younger–Kasami algorithm.
2. Reduction of the parsing problem for context-free grammars to matrix multiplication (Valiant's algorithm).
3. Greibach normal form.
4. The Lambek calculus, Lambek categorial grammars. Equivalence of Lambek grammars and context-free grammars (Pentus' theorem).
5. Proof nets for the Lambek calculus.
6. Polynomial translation of Lambek grammars with one division into context-free grammars.
7. NP-completeness of the derivability problem for the Lambek calculus.
8. Polynomial algorithm for Lambek grammars with bounded depth.
9. Tree-adjoining grammars (TAG).
10. Noncontracting grammars and their generation of PSPACE-complete languages. Polynomial-time parsing algorithm for a fixed growing grammar.
11. Generative grammars (type-0 grammars in Chomsky hierarchy). Algorithmic undecidability of the parsing problem for Lambek grammars with additional axioms (including the single-division fragment).
12. Undecidability of the totality problem (generation of all words over a given alphabet) for context-free grammars. Languages defined by Lambek grammars with Kleene iteration.

Lecturers
Kuznetsov Stepan Lvovich
Pshenitsyn Tikhon Grigor'evich

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