Курс С. Л. Кузнецова и Т. Г. Пшеницына "Алгоритмические вопросы для формальных грамматик" 18 сентября–25 декабря 2025 г., МИАН, комн. 104 (ул. Губкина, 8), г. Москва
Просьба ко всем участникам, в том числе смотрящим видеозаписи, зарегистрироваться по этой ссылке.
Теория формальных грамматик находится на пересечении математической логики, теоретической информатики и лингвистики. Формальные грамматики используются для описания как естественных языков, так и языков машинных (например, языков программирования).
В курсе рассматриваются два семейства грамматических формализмов — порождающие грамматики Хомского и категориальные грамматики Ламбека. Особое внимание уделяется грамматикам, для которых существуют эффективные (работающие за полиномиальное время) алгоритмы разбора, нетривиальным образом использующие идеи динамического программирования. Такие грамматики представляют наибольший интерес для приложений.
Программа
Контекстно-свободные грамматики. Нормальная форма Хомского. Алгоритм Кока-Янгера-Касами.
Исчисление Ламбека, категориальные грамматики Ламбека. Совпадение классов языков, задаваемых грамматиками Ламбека и контекстно-свободными грамматиками (теорема Пентуса).
$NP$-полнота задачи выводимости в исчислении Ламбека.
Полиномиальный алгоритм для грамматик Ламбека с ограниченной глубиной типов.
Полиномиальное преобразование грамматик Ламбека с одним делением в контекстно-свободные грамматики.
Порождающие грамматики общего вида (грамматики типа $0$). Алгоритмическая неразрешимость задачи синтаксического разбора для грамматик Ламбека с дополнительными аксиомами (в т.ч. во фрагменте с одним делением).
Неукорачивающие грамматики, порождение ими $PSPACE$-полных языков. Полиномиальный алгоритм разбора для фиксированной удлиняющей грамматики.
Алгоритмическая неразрешимость задачи тотальности (порождения всех слов в данном алфавите) для контекстно-свободных грамматик. Языки, задаваемые грамматиками Ламбека с итерацией Клини.
RSS: Ближайшие семинары
Лекторы