|
Курс М. Р. Пентуса "Контекстно-свободные языки"
13 февраля–21 мая 2024 г., МИАН, комн. 430 (ул. Губкина, 8), г. Москва
Просьба ко всем участникам, в том числе смотрящим видеозаписи,
зарегистрироваться по этой ссылке.
Контекстно-свободные грамматики находят применение в информатике (например, в интерпретаторах и компиляторах), а также в лингвистике.
В курсе будут приведены доказательства основных классических математических результатов о контекстно-свободных грамматиках и автоматах с магазинной памятью, в том числе теорем о дополнении и пересечении, о представлении языков посредством гомоморфизмов, о неразрешимости проблемы эквивалентности грамматик и некоторых других проблем.
Программа
- Формальные языки.
- Контекстно-свободные грамматики.
- Языки Дика и Лукасевича.
- Нормальные формы контекстно-свободных грамматик.
- Лемма о разрастании для контекстно-свободных языков.
- Автоматы с магазинной памятью. Характеризация контекстно-свободных языков.
- Свойства замкнутости класса контекстно-свободных языков. Пересечение контекстно-свободного языка с автоматным языком.
- Гомоморфизмы и контекстно-свободные языки.
- Теорема Хомского-Шютценберже.
- Детерминированные контекстно-свободные языки.
- Алгоритмически разрешимые проблемы. Неукорачивающие грамматики. Проблема выводимости слова. Проблема пустоты языка. Проблема бесконечности языка. Проблема эквивалентности конечных автоматов.
Проблема эквивалентности детерминированных МП-автоматов.
- Алгоритмически неразрешимые проблемы. Пересечение контекстносвободных языков. Дополнение контекстно-свободного языка. Проблема автоматности. Проблемы контекстной свободности.
 Объявление:
30 апреля, 7 мая и 14 мая лекций не будет.
Следующая лекция будет 21.05.2024.
Контекстно-свободные языки. Сборник задач
Порождающие грамматики (листок к просеминару)
Теория формальных языков. Учебное пособие
Программа
Лектор
Пентус Мати Рейнович
Финансовая поддержка
Курс проводится при финансовой поддержке Минобрнауки России (грант на создание и развитие МЦМУ МИАН, соглашение № 075-15-2022-265).
Организации
Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
Математический центр мирового уровня «Математический институт им. В.А. Стеклова Российской академии наук» (МЦМУ МИАН) |
|
| Курс М. Р. Пентуса "Контекстно-свободные языки", г. Москва, 13 февраля–21 мая 2024 г. |
|
|
21 мая 2024 г. (вт) |
 |
| 1. |
Лекция 12. Контекстно-свободные языки. Теорема Парика
М. Р. Пентус
21 мая 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
23 апреля 2024 г. (вт) |
|
| 2. |
Лекция 11. Контекстно-свободные языки. Разрешимость проблемы пустоты языка, проблемы бесконечности языка и проблемы выводимости слова. Автоматность контекстно-свободного языка над однобуквенным алфавитом
М. Р. Пентус
23 апреля 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
16 апреля 2024 г. (вт) |
|
| 3. |
Лекция 10. Контекстно-свободные языки. Неразрешимость проблемы эквивалентности грамматик и проблемы автоматности
М. Р. Пентус
16 апреля 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
9 апреля 2024 г. (вт) |
|
| 4. |
Лекция 9. Контекстно-свободные языки. Проблема соответствий Поста
М. Р. Пентус
9 апреля 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
2 апреля 2024 г. (вт) |
|
| 5. |
Лекция 8. Контекстно-свободные языки. Дополнение детерминированного контекстно-свободного языка
М. Р. Пентус
2 апреля 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
26 марта 2024 г. (вт) |
|
| 6. |
Лекция 7. Контекстно-свободные языки. Детерминированные автоматы с магазинной памятью
М. Р. Пентус
26 марта 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
19 марта 2024 г. (вт) |
|
| 7. |
Лекция 6. Контекстно-свободные языки. Теорема Хомского-Шютценберже
М. Р. Пентус
19 марта 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
12 марта 2024 г. (вт) |
|
| 8. |
Лекция 5. Контекстно-свободные языки. Пересечение контекстно-свободного языка с автоматным языком
М. Р. Пентус
12 марта 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
5 марта 2024 г. (вт) |
|
| 9. |
Лекция 4. Контекстно-свободные языки. Автоматы с магазинной памятью
М. Р. Пентус
5 марта 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
27 февраля 2024 г. (вт) |
|
| 10. |
Лекция 3. Контекстно-свободные языки. Лемма о разрастании
М. Р. Пентус
27 февраля 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
20 февраля 2024 г. (вт) |
|
| 11. |
Лекция 2. Контекстно-свободные языки. Нормальные формы Хомского и Грейбах
М. Р. Пентус
20 февраля 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
13 февраля 2024 г. (вт) |
|
| 12. |
Лекция 1. Контекстно-свободные языки. Языки Дика и Лукасевича
М. Р. Пентус
13 февраля 2024 г. 18:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)
|
|
|
|
|
|
|
Обратная связь: