Теория формальных языков

Программа курса:

* Языки и yes/no-задачи. Теоретико-множественное доказательство
невозможности описания языков.
* Детерминированные конечные автоматы. Принятие слова.
* Эквивалентность состояний. Минимизация ДКА.
* Правые контексты.
* Динамическое программирование по ДКА.
* Прямое произведение ДКА.
* Недетерминированные конечные автоматы с eps-переходами. Принятие слова.
* Детерминизация НКА.
* Академические регулярные выражения.
* Теорема Клини — эквивалентность КА и АРВ.
* Операции над языками. Свойства регулярных языков.
* Лемма о разрастании.
* КС-грамматики.
* Вывод, левосторонний вывод, дерево разбора.
* Однозначные КС-грамматики.
* Вложенность регулярных языков в КС-языки.
* КС-грамматики с АРВ в правой части.
* Нормальная форма Хомского.
* Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций,
терминалов в длинных продукциях, длинных продукций.
* Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
* Лемма о разрастании для КС-грамматик
* Автоматы с магазинной памятью
* Эквивалентность МП-автоматов и КС-грамматик
* Иерархия Хомского