We kindly ask all participants, including remote ones and those
watching recorded videos, to register at this link.
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
- Formal languages.
- Context-free grammars.
- Dyck languages and Łukasiewicz languages.
- Normal forms of context-free grammars.
- The pumping lemma for context-free languages.
- Pushdown automata. Characterization of context-free languages.
- Closure properties for the class of context-free languages. The intersection of a
context-free language with a regular language.
- Homomorphisms and context-free languages.
- The Chomsky-Schützenberger theorem.
- Deterministic context-free languages.
- 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.
- Algorithmically undecidable problems. The intersection of context-free
languages. The complement of a context-free language. The regularity problem.
Context-freeness problems.
 RSS: Forthcoming seminars
 Lecturer
Pentus Mati Reinovich
Organizations
Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
Steklov International Mathematical Center |
