Формальные языки, 5 курс, весна 2016

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

Практика: Екатерина Вербицкая, Михаил Слабодкин (slabodkinm@gmail.com).

План

Лекция 1

• Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
• Детерминированные конечные автоматы. Принятие слова.
• Эквивалентность состояний. Минимизация ДКА.

Лекция 2

• Правые контексты.
• Эквивалентность ДКА.
• Прямое произведение ДКА.
• Динамическое программирование по ДКА.

Лекция 3

• Академические регулярные выражения.
• Теорема Клини — эквивалентность КА и АРВ.

Лекция 4

• Операции над языками. Свойства регулярных языков.
• Лемма о разрастании.

Лекция 5

• КС-грамматики.
• Вывод, левосторонний вывод, дерево разбора.
• Однозначные КС-грамматики.
• Вложенность регулярных языков в КС-языки.

Лекция 6

• Нормальная форма Хомского.
• Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
• Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.

Лекция 7

• Лемма о разрастании для КС-грамматик
• Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию

Лекция 8

• Эквивалентность МП-автоматов и КС-грамматик
• Детеримированные автоматы с магазинной памятью, прием по терминальному состоянию
• Соотношение регулярных, ДМП- и КС-языков

Список вопросов

UPDATE: Билет №14 появился в этом документе позже, заметьте его, пожалуйста.

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

Подгруппа Михаила Слабодкина

Результаты

Подгруппа Екатерины Вербицкой

Результаты

Ссылки

• Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
• [1]
• [2]
• [3]
• [4]