Формальные языки, 2 курс, весна 2016 — различия между версиями
Материал из SEWiki
(→К занятиям Николая Карпова) |
Darnley (обсуждение | вклад) (→План) |
||
Строка 14: | Строка 14: | ||
* Прямое произведение ДКА. | * Прямое произведение ДКА. | ||
* Динамическое программирование по ДКА. | * Динамическое программирование по ДКА. | ||
+ | Лекция 3 | ||
+ | * Академические регулярные выражения. | ||
+ | * Теорема Клини — эквивалентность КА и АРВ. | ||
+ | Лекция 4 | ||
+ | * Операции над языками. Свойства регулярных языков. | ||
+ | * Лемма о разрастании. | ||
+ | Лекция 5 | ||
+ | * КС-грамматики. | ||
+ | * Вывод, левосторонний вывод, дерево разбора. | ||
+ | * Однозначные КС-грамматики. | ||
+ | * Вложенность регулярных языков в КС-языки. | ||
+ | Лекция 6 | ||
+ | * КС-грамматики с АРВ в правой части. | ||
+ | * Нормальная форма Хомского. | ||
+ | * Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | ||
+ | * Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
+ | Лекция 7 | ||
+ | * Лемма о разрастании для КС-грамматик | ||
+ | * Автоматы с магазинной памятью | ||
== К занятиям Николая Карпова == | == К занятиям Николая Карпова == |
Версия 01:31, 5 апреля 2016
Лекции: Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)
Практика: Николай Карпов (I подгруппа), Михаил Слабодкин (slabodkinm@gmail.com) (II подгруппа).
Содержание
План
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
Лекция 2
- Правые контексты.
- Эквивалентность ДКА.
- Прямое произведение ДКА.
- Динамическое программирование по ДКА.
Лекция 3
- Академические регулярные выражения.
- Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
- Операции над языками. Свойства регулярных языков.
- Лемма о разрастании.
Лекция 5
- КС-грамматики.
- Вывод, левосторонний вывод, дерево разбора.
- Однозначные КС-грамматики.
- Вложенность регулярных языков в КС-языки.
Лекция 6
- КС-грамматики с АРВ в правой части.
- Нормальная форма Хомского.
- Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
Лекция 7
- Лемма о разрастании для КС-грамматик
- Автоматы с магазинной памятью
К занятиям Николая Карпова
Домашние задания
Осторожно, теоретически могут быть ссылки на старые версии - актуальные ищите в разделе "Все материалы и табличка" выше.
№ | Дата |
---|---|
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 |