Формальные языки 2MIT весна 2018 — различия между версиями
Материал из SEWiki
Eran (обсуждение | вклад) (→Практика Слабодкин) |
Darnley (обсуждение | вклад) (→Список билетов на экзамене) |
||
| (не показаны 4 промежуточные версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Лекции == | == Лекции == | ||
Преподаватель: Дворкин Михаил Эдуардович ('''mikhail.dvorkin@gmail.com''') | Преподаватель: Дворкин Михаил Эдуардович ('''mikhail.dvorkin@gmail.com''') | ||
| + | |||
| + | == Список билетов на экзамене == | ||
| + | |||
| + | # Детерминированные конечные автоматы. Принятие слова. Эквивалентность состояний. Минимизация ДКА. | ||
| + | # Правые контексты. Прямое произведение ДКА. Динамическое программирование по ДКА. | ||
| + | # Недетерминированные КА, их соотношение с детерминированными. Распознавание слова НКА. Детерминизация. Эквивалентность ДКА и НКА. | ||
| + | # Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ. | ||
| + | # Лемма о разрастании для ДКА. | ||
| + | # КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Однозначные КС-грамматики. | ||
| + | # Нормальная форма Хомского. Все этапы алгоритма приведения к НФХ. | ||
| + | # Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
| + | # Лемма о разрастании для КС-грамматик. | ||
| + | # Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию. Эквивалентность МП-автоматов и КС-грамматик. | ||
| + | # Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков. | ||
| + | # Иерархия Хомского. Регулярные грамматики, эквивалентность ДКА. Неограниченные грамматики, эквивалентность машинам Тьюринга. | ||
| + | # Контекстно-зависимые грамматики, неукорачивающие грамматики. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней. | ||
== Практика Слабодкин == | == Практика Слабодкин == | ||
| Строка 15: | Строка 30: | ||
* [[Медиа:FL5_spring2018.pdf | Задания к практике №5]] | * [[Медиа:FL5_spring2018.pdf | Задания к практике №5]] | ||
* [[Медиа:FL6_spring2018.pdf | Задания к практике №6]] | * [[Медиа:FL6_spring2018.pdf | Задания к практике №6]] | ||
| + | * [[Медиа:FL7_spring2018.pdf | Задание к практике №7]] | ||
== Практика Вербицкая == | == Практика Вербицкая == | ||
| Строка 26: | Строка 42: | ||
[https://docs.google.com/spreadsheets/d/1I-UG1UHBldLlC0EwRRlbyVJJKvVqH5X6VHMMueEYYM0/ Таблица с результатами] | [https://docs.google.com/spreadsheets/d/1I-UG1UHBldLlC0EwRRlbyVJJKvVqH5X6VHMMueEYYM0/ Таблица с результатами] | ||
| − | + | [http://mit.spbau.ru/sewiki/images/9/98/Fl.pdf Все задания] | |
Текущая версия на 12:31, 18 июня 2018
Содержание
Лекции
Преподаватель: Дворкин Михаил Эдуардович (mikhail.dvorkin@gmail.com)
Список билетов на экзамене
- Детерминированные конечные автоматы. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
- Правые контексты. Прямое произведение ДКА. Динамическое программирование по ДКА.
- Недетерминированные КА, их соотношение с детерминированными. Распознавание слова НКА. Детерминизация. Эквивалентность ДКА и НКА.
- Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ.
- Лемма о разрастании для ДКА.
- КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Однозначные КС-грамматики.
- Нормальная форма Хомского. Все этапы алгоритма приведения к НФХ.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
- Лемма о разрастании для КС-грамматик.
- Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию. Эквивалентность МП-автоматов и КС-грамматик.
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
- Иерархия Хомского. Регулярные грамматики, эквивалентность ДКА. Неограниченные грамматики, эквивалентность машинам Тьюринга.
- Контекстно-зависимые грамматики, неукорачивающие грамматики. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней.
Практика Слабодкин
Преподаватель: Слабодкин Михаил Григорьевич(slabodkinm@gmail.com )
- Задания к практике №1
- Задания к практике №2
- Задания к практике №3
- Задания к практике №4
- Задания к практике №5
- Задания к практике №6
- Задание к практике №7
Практика Вербицкая
Преподаватель: Вербицкая Екатерина Андреевна (kajigor@gmail.com)
Практика Палецких
Преподаватель: Палецких Алексей Андреевич (a.paletskikh@gmail.com)
