Course by M. R. Pentus "Context-free languages" February 13–May 21, 2024, Steklov Mathematical Institute, Room 430 (8 Gubkina)
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.
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 |
|
Course by M. R. Pentus "Context-free languages", February 13–May 21, 2024 |
|
|
May 21, 2024 (Tue) |
 |
1. |
Lecture 12. Context-free languages M. R. Pentus May 21, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
April 23, 2024 (Tue) |
 |
2. |
Lecture 11. Context-free languages M. R. Pentus April 23, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
April 16, 2024 (Tue) |
 |
3. |
Lecture 10. Context-free languages M. R. Pentus April 16, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
April 9, 2024 (Tue) |
 |
4. |
Lecture 9. Context-free languages M. R. Pentus April 9, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
April 2, 2024 (Tue) |
 |
5. |
Lecture 8. Context-free languages M. R. Pentus April 2, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
March 26, 2024 (Tue) |
 |
6. |
Lecture 7. Context-free languages M. R. Pentus March 26, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
March 19, 2024 (Tue) |
 |
7. |
Lecture 6. Context-free languages M. R. Pentus March 19, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
March 12, 2024 (Tue) |
 |
8. |
Lecture 5. Context-free languages M. R. Pentus March 12, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
March 5, 2024 (Tue) |
 |
9. |
Lecture 4. Context-free languages M. R. Pentus March 5, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
February 27, 2024 (Tue) |
 |
10. |
Lecture 3. Context-free languages M. R. Pentus February 27, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
February 20, 2024 (Tue) |
 |
11. |
Lecture 2. Context-free languages M. R. Pentus February 20, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
|
|
February 13, 2024 (Tue) |
 |
12. |
Lecture 1. Context-free languages M. R. Pentus February 13, 2024 18:00, Steklov Mathematical Institute, Room 430 (8 Gubkina)
|
|
|
|
 |
|