Формальные языки, 5 курс, весна 2016 — различия между версиями
Материал из SEWiki
Darnley (обсуждение | вклад) (→План) |
Darnley (обсуждение | вклад) |
||
Строка 26: | Строка 26: | ||
* Вложенность регулярных языков в КС-языки. | * Вложенность регулярных языков в КС-языки. | ||
Лекция 6 | Лекция 6 | ||
− | |||
* Нормальная форма Хомского. | * Нормальная форма Хомского. | ||
* Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | * Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. |
Версия 02:18, 5 апреля 2016
Лекции: Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)
Практика: Екатерина Вербицкая, Михаил Слабодкин (slabodkinm@gmail.com).
План
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
Лекция 2
- Правые контексты.
- Эквивалентность ДКА.
- Прямое произведение ДКА.
- Динамическое программирование по ДКА.
Лекция 3
- Академические регулярные выражения.
- Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
- Операции над языками. Свойства регулярных языков.
- Лемма о разрастании.
Лекция 5
- КС-грамматики.
- Вывод, левосторонний вывод, дерево разбора.
- Однозначные КС-грамматики.
- Вложенность регулярных языков в КС-языки.
Лекция 6
- Нормальная форма Хомского.
- Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.