Формальные языки 2MIT весна 2018

Лекции

Преподаватель: Дворкин Михаил Эдуардович (mikhail.dvorkin@gmail.com)

Список билетов на экзамене

1. Детерминированные конечные автоматы. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
2. Правые контексты. Прямое произведение ДКА. Динамическое программирование по ДКА.
3. Недетерминированные КА, их соотношение с детерминированными. Распознавание слова НКА. Детерминизация. Эквивалентность ДКА и НКА.
4. Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ.
5. Лемма о разрастании для ДКА.
6. КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Однозначные КС-грамматики.
7. Нормальная форма Хомского. Все этапы алгоритма приведения к НФХ.
8. Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
9. Лемма о разрастании для КС-грамматик.
10. Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию. Эквивалентность МП-автоматов и КС-грамматик.
11. Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
12. Иерархия Хомского. Регулярные грамматики, эквивалентность ДКА. Неограниченные грамматики, эквивалентность машинам Тьюринга.
13. Контекстно-зависимые грамматики, неукорачивающие грамматики. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней.

Практика Слабодкин

Преподаватель: Слабодкин Михаил Григорьевич(slabodkinm@gmail.com )

Таблица с результатами

• Задания к практике №1
• Задания к практике №2
• Задания к практике №3
• Задания к практике №4
• Задания к практике №5
• Задания к практике №6
• Задание к практике №7

Практика Вербицкая

Преподаватель: Вербицкая Екатерина Андреевна (kajigor@gmail.com)

Практика Палецких

Преподаватель: Палецких Алексей Андреевич (a.paletskikh@gmail.com)

Таблица с результатами

Все задания