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