Формальные языки, 2 курс, весна 2016
Материал из SEWiki
Лекции: Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)
Практика: Николай Карпов (I подгруппа), Михаил Слабодкин (slabodkinm@gmail.com) (II подгруппа).
Конспект http://yeputons.net/spbau/term4-formal_languages-lectures.pdf
Содержание
План
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
Лекция 2
- Правые контексты.
- Эквивалентность ДКА.
- Прямое произведение ДКА.
- Динамическое программирование по ДКА.
Лекция 3
- Академические регулярные выражения.
- Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
- Операции над языками. Свойства регулярных языков.
- Лемма о разрастании.
Лекция 5
- КС-грамматики.
- Вывод, левосторонний вывод, дерево разбора.
- Однозначные КС-грамматики.
- Вложенность регулярных языков в КС-языки.
Лекция 6
- Нормальная форма Хомского.
- Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
Лекция 7
- Лемма о разрастании для КС-грамматик
- Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию
Лекция 8
- Эквивалентность МП-автоматов и КС-грамматик
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема
- Соотношение регулярных, ДМП- и КС-языков
Лекция 9
- Иерархия Хомского
- Регулярные грамматики, эквивалентность ДКА
- Контекстно-зависимые грамматики, неукорачивающие грамматики
- Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней
- Неограниченные грамматики, эквивалентность машинам Тьюринга
Лекция 10 (правильнее: 6.5)
- Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ.
Список вопросов
UPDATE: Билет №14 появился в этом документе позже, заметьте его, пожалуйста. UPDATE: Билет №15 уточнён.
- Детерминированные конечные автоматы. Определение. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
- Правые контексты. Связь с размером минимального ДКА. Прямое произведение ДКА. Динамическое программирование по ДКА, примеры.
- Недетерминированные конечные автоматы с eps-переходами. Детерминизация НКА.
- Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из КА в АРВ.
- Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из АРВ в КА.
- Лемма о разрастании для регулярных языков.
- КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Вложенность регулярных языков в КС-языки.
- Нормальная форма Хомского. Приведение к ней: удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Нормальная и ослабленная нормальная форма Грейбах. Приведение к ослабленной НФГ.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
- Лемма о разрастании для КС-языков.
- Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из АМП в КСГ.
- Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из КСГ в АМП.
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
- Иерархия Хомского. Регулярные грамматики, их эквивалентность регулярным языкам. Контекстно-зависимые грамматики, неукорачивающие грамматики, их эквивалентность.
- Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней
К занятиям Николая Карпова
Домашние задания
Осторожно, теоретически могут быть ссылки на старые версии - актуальные ищите в разделе "Все материалы и табличка" выше.
| № | Дата |
|---|---|
| 1 | На 19.02.2016 |
| 2 | На 26.02.2016 |
| 3 | На 04.03.2016 |
| 4 | На 11.03.2016 |
| 5 | На 18.03.2016 |
| 6 | На 25.03.2016 |
| 7 | На 01.04.2016 |
| 8 | На 08.04.2016 |
| 9 | На 22.04.2016 |
| 10 | На 29.04.2016 |
| 11 | На 06.05.2016 |
