Формальные языки, 5 курс, весна 2016 — различия между версиями
Материал из SEWiki
Darnley (обсуждение | вклад) (Новая страница: «'''Лекции:''' Михаил Эдуардович Дворкин (<b>mikhail.dvorkin@gmail.com</b>) '''Практика:''' Екатерина Вербицк…») |
Darnley (обсуждение | вклад) |
||
(не показано 7 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
'''Лекции:''' Михаил Эдуардович Дворкин (<b>mikhail.dvorkin@gmail.com</b>) | '''Лекции:''' Михаил Эдуардович Дворкин (<b>mikhail.dvorkin@gmail.com</b>) | ||
− | '''Практика:''' Екатерина Вербицкая, Михаил Слабодкин. | + | '''Практика:''' Екатерина Вербицкая, Михаил Слабодкин (slabodkinm@gmail.com). |
== План == | == План == | ||
Строка 14: | Строка 14: | ||
* Прямое произведение ДКА. | * Прямое произведение ДКА. | ||
* Динамическое программирование по ДКА. | * Динамическое программирование по ДКА. | ||
+ | Лекция 3 | ||
+ | * Академические регулярные выражения. | ||
+ | * Теорема Клини — эквивалентность КА и АРВ. | ||
+ | Лекция 4 | ||
+ | * Операции над языками. Свойства регулярных языков. | ||
+ | * Лемма о разрастании. | ||
+ | Лекция 5 | ||
+ | * КС-грамматики. | ||
+ | * Вывод, левосторонний вывод, дерево разбора. | ||
+ | * Однозначные КС-грамматики. | ||
+ | * Вложенность регулярных языков в КС-языки. | ||
+ | Лекция 6 | ||
+ | * Нормальная форма Хомского. | ||
+ | * Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | ||
+ | * Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
+ | Лекция 7 | ||
+ | * Лемма о разрастании для КС-грамматик | ||
+ | * Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию | ||
+ | Лекция 8 | ||
+ | * Эквивалентность МП-автоматов и КС-грамматик | ||
+ | * Детеримированные автоматы с магазинной памятью, прием по терминальному состоянию | ||
+ | * Соотношение регулярных, ДМП- и КС-языков | ||
+ | |||
+ | == Список вопросов == | ||
+ | |||
+ | UPDATE: Билет №14 появился в этом документе позже, заметьте его, пожалуйста. | ||
+ | |||
+ | # Детерминированные конечные автоматы. Определение. Принятие слова. Эквивалентность состояний. Минимизация ДКА. | ||
+ | # Правые контексты. Связь с размером минимального ДКА. Прямое произведение ДКА. Динамическое программирование по ДКА, примеры. | ||
+ | # Недетерминированные конечные автоматы с eps-переходами. Детерминизация НКА. | ||
+ | # Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из КА в АРВ. | ||
+ | # Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из АРВ в КА. | ||
+ | # Лемма о разрастании для регулярных языков. | ||
+ | # КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Вложенность регулярных языков в КС-языки. | ||
+ | # Нормальная форма Хомского. Приведение к ней: удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | ||
+ | # Нормальная и ослабленная нормальная форма Грейбах. Приведение к ослабленной НФГ. | ||
+ | # Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
+ | # Лемма о разрастании для КС-языков. | ||
+ | # Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из АМП в КСГ. | ||
+ | # Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из КСГ в АМП. | ||
+ | # Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков. | ||
+ | # Иерархия Хомского. | ||
+ | # Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней | ||
+ | |||
+ | |||
+ | |||
+ | == Подгруппа Михаила Слабодкина == | ||
+ | |||
+ | [https://docs.google.com/spreadsheets/d/1A_IpQrFM7Qf524oY79ONEvnFxu2zw8bRGx8-XEQm3Rg Результаты] | ||
+ | |||
+ | == Подгруппа Екатерины Вербицкой == | ||
+ | |||
+ | [https://docs.google.com/spreadsheets/d/15YLkdBCmvZyICh9cFCclnz3iXzw_O1PZ-QuOcLo2Y7A/edit?usp=sharing_eid&invite=CL-Lgs8J&ts=56d60b0c Результаты] | ||
== Ссылки == | == Ссылки == |
Текущая версия на 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-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Нормальная и ослабленная нормальная форма Грейбах. Приведение к ослабленной НФГ.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
- Лемма о разрастании для КС-языков.
- Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из АМП в КСГ.
- Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из КСГ в АМП.
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
- Иерархия Хомского.
- Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней