Просьба ко всем участникам, в том числе смотрящим видеозаписи,
зарегистрироваться по этой ссылке.
Контекстно-свободные грамматики находят применение в информатике (например, в интерпретаторах и компиляторах), а также в лингвистике.
В курсе будут приведены доказательства основных классических математических результатов о контекстно-свободных грамматиках и автоматах с магазинной памятью, в том числе теорем о дополнении и пересечении, о представлении языков посредством гомоморфизмов, о неразрешимости проблемы эквивалентности грамматик и некоторых других проблем.
Программа
- Формальные языки.
- Контекстно-свободные грамматики.
- Языки Дика и Лукасевича.
- Нормальные формы контекстно-свободных грамматик.
- Лемма о разрастании для контекстно-свободных языков.
- Автоматы с магазинной памятью. Характеризация контекстно-свободных языков.
- Свойства замкнутости класса контекстно-свободных языков. Пересечение контекстно-свободного языка с автоматным языком.
- Гомоморфизмы и контекстно-свободные языки.
- Теорема Хомского-Шютценберже.
- Детерминированные контекстно-свободные языки.
- Алгоритмически разрешимые проблемы. Неукорачивающие грамматики. Проблема выводимости слова. Проблема пустоты языка. Проблема бесконечности языка. Проблема эквивалентности конечных автоматов.
Проблема эквивалентности детерминированных МП-автоматов.
- Алгоритмически неразрешимые проблемы. Пересечение контекстносвободных языков. Дополнение контекстно-свободного языка. Проблема автоматности. Проблемы контекстной свободности.
 Объявление:
30 апреля, 7 мая и 14 мая лекций не будет.
Следующая лекция будет 21.05.2024.
Контекстно-свободные языки. Сборник задач
Порождающие грамматики (листок к просеминару)
Теория формальных языков. Учебное пособие
 RSS: Ближайшие семинары
Лектор
Пентус Мати Рейнович
Организации
Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
Математический центр мирового уровня «Математический институт им. В.А. Стеклова Российской академии наук» (МЦМУ МИАН) |
