Формальные языки, 5 курс, 2 семестр, 2016/17 — различия между версиями
Материал из SEWiki
(→Практика Слабодкин) |
|||
(не показано 13 промежуточных версий этого же участника) | |||
Строка 9: | Строка 9: | ||
* Детерминированные конечные автоматы. Принятие слова. | * Детерминированные конечные автоматы. Принятие слова. | ||
* Эквивалентность состояний. Минимизация ДКА. | * Эквивалентность состояний. Минимизация ДКА. | ||
+ | Лекция 2 | ||
+ | * Правые контексты. | ||
+ | * Эквивалентность ДКА. | ||
+ | * Прямое произведение ДКА. | ||
+ | * Динамическое программирование по ДКА. | ||
+ | Лекция 3 | ||
+ | * Академические регулярные выражения. | ||
+ | * Теорема Клини — эквивалентность КА и АРВ. | ||
+ | Лекция 4 | ||
+ | * Операции над языками. Свойства регулярных языков. | ||
+ | * Лемма о разрастании. | ||
+ | Лекция 5 | ||
+ | * КС-грамматики. | ||
+ | * Вывод, левосторонний вывод, дерево разбора. | ||
+ | * Однозначные КС-грамматики. | ||
+ | * Вложенность регулярных языков в КС-языки. | ||
+ | Лекция 6 | ||
+ | * Нормальная форма Хомского. | ||
+ | * Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | ||
+ | * Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
+ | * Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ. | ||
+ | Лекция 7 | ||
+ | * Лемма о разрастании для КС-грамматик | ||
+ | * Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию | ||
+ | Лекция 8 | ||
+ | * Эквивалентность МП-автоматов и КС-грамматик | ||
+ | * Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема | ||
+ | * Соотношение регулярных, ДМП- и КС-языков | ||
+ | Лекция 9 | ||
+ | * Иерархия Хомского | ||
+ | * Регулярные грамматики, эквивалентность ДКА | ||
+ | * Контекстно-зависимые грамматики, неукорачивающие грамматики | ||
+ | * Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней | ||
+ | * Неограниченные грамматики, эквивалентность машинам Тьюринга | ||
== Практика Слабодкин == | == Практика Слабодкин == | ||
Строка 19: | Строка 53: | ||
[[Медиа:FL_S_3.pdf|Практика 3]] | [[Медиа:FL_S_3.pdf|Практика 3]] | ||
+ | |||
+ | [[Медиа:FL_S_4.pdf|Практика 4]] | ||
+ | |||
+ | [[Медиа:FL_S_5.pdf|Практика 5]] | ||
+ | |||
+ | [[Медиа:FL_S_6.pdf|Практика 6]] | ||
+ | |||
+ | [[Медиа:FL_S_7.pdf|Практика 7]] | ||
+ | |||
+ | [[Медиа:FL_S_8.pdf|Практика 8]] | ||
+ | |||
+ | [[Медиа:FL_S_9.pdf|Практика 9]] | ||
+ | |||
+ | [[Медиа:FL_S_10.pdf|Практика 10]] | ||
+ | |||
+ | [[Медиа:FL_S_11.pdf|Практика 11]] | ||
== Практика Вербицкая == | == Практика Вербицкая == | ||
Строка 27: | Строка 77: | ||
[[Медиа:FL_V_2.pdf|Практика 2]] | [[Медиа:FL_V_2.pdf|Практика 2]] | ||
+ | |||
+ | [[Медиа:FL_V_3.pdf|Практика 3]] | ||
+ | |||
+ | [[Медиа:FL_V_4.pdf|Практика 4]] | ||
+ | |||
+ | [[Медиа:FL_V_5.pdf|Практика 5]] | ||
+ | |||
+ | [[Медиа:FL_V_6.pdf|Практика 6]] | ||
+ | |||
+ | [[Медиа:FL_V_7.pdf|Практика 7]] | ||
+ | |||
+ | [[Медиа:FL_V_8.pdf|Практика 8]] | ||
+ | |||
+ | [[Медиа:FL_V_9.pdf|Практика 9]] | ||
+ | |||
+ | [[Медиа:FL_V_10.pdf|Практика 10]] | ||
== Ссылки == | == Ссылки == |
Текущая версия на 00:08, 18 мая 2017
Лектор — Дворкин Михаил Эдуардович, mikhail.dvorkin@gmail.com
Практика — Михаил Слабодкин (slabodkinm@gmail.com), Екатерина Вербицкая
Содержание
Лекции
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
Лекция 2
- Правые контексты.
- Эквивалентность ДКА.
- Прямое произведение ДКА.
- Динамическое программирование по ДКА.
Лекция 3
- Академические регулярные выражения.
- Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
- Операции над языками. Свойства регулярных языков.
- Лемма о разрастании.
Лекция 5
- КС-грамматики.
- Вывод, левосторонний вывод, дерево разбора.
- Однозначные КС-грамматики.
- Вложенность регулярных языков в КС-языки.
Лекция 6
- Нормальная форма Хомского.
- Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
- Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ.
Лекция 7
- Лемма о разрастании для КС-грамматик
- Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию
Лекция 8
- Эквивалентность МП-автоматов и КС-грамматик
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема
- Соотношение регулярных, ДМП- и КС-языков
Лекция 9
- Иерархия Хомского
- Регулярные грамматики, эквивалентность ДКА
- Контекстно-зависимые грамматики, неукорачивающие грамматики
- Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней
- Неограниченные грамматики, эквивалентность машинам Тьюринга