Формальные языки 5SE весна 2018 — различия между версиями
Материал из SEWiki
V.makeev (обсуждение | вклад) м |
Darnley (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
== Лекции == | == Лекции == | ||
| − | Преподаватель: Дворкин Михаил Эдуардович ( | + | Преподаватель: Дворкин Михаил Эдуардович (<code>mikhail.dvorkin@gmail.com</code>) |
| − | |||
| − | + | ==== Список билетов на экзамене ==== | |
| − | + | # Детерминированные конечные автоматы. Принятие слова. Эквивалентность состояний. Минимизация ДКА. | |
| + | # Правые контексты. Прямое произведение ДКА. Динамическое программирование по ДКА. | ||
| + | # Недетерминированные КА, их соотношение с детерминированными. Распознавание слова НКА. Детерминизация. Эквивалентность ДКА и НКА. | ||
| + | # Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ. | ||
| + | # Лемма о разрастании для ДКА. | ||
| + | # КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Однозначные КС-грамматики. | ||
| + | # Нормальная форма Хомского. Все этапы алгоритма приведения к НФХ. | ||
| + | # Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
| + | # Лемма о разрастании для КС-грамматик. | ||
| + | # Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию. Эквивалентность МП-автоматов и КС-грамматик. | ||
| + | # Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков. | ||
| + | # Иерархия Хомского. Регулярные грамматики, эквивалентность ДКА. Неограниченные грамматики, эквивалентность машинам Тьюринга. | ||
| + | # Контекстно-зависимые грамматики, неукорачивающие грамматики. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней. | ||
| − | |||
| − | == Ссылки == | + | ==== Ссылки ==== |
| + | |||
* Важная книга: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений. | * Важная книга: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений. | ||
| − | * [http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков] | + | * [http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков neerc.ifmo.ru] |
* [http://www.ics.uci.edu/~goodrich/teach/cs162/notes/] | * [http://www.ics.uci.edu/~goodrich/teach/cs162/notes/] | ||
* [http://www.eecs.wsu.edu/~ananth/CptS317/] | * [http://www.eecs.wsu.edu/~ananth/CptS317/] | ||
* [http://users.utu.fi/jkari/automata/fullnotes.pdf] | * [http://users.utu.fi/jkari/automata/fullnotes.pdf] | ||
* [http://yeputons.net/spbau/term4/formal_languages-lectures.pdf] | * [http://yeputons.net/spbau/term4/formal_languages-lectures.pdf] | ||
| + | |||
| + | == Практика == | ||
| + | |||
| + | === Слабодкин Михаил === | ||
| + | |||
| + | Контакты: <code>slabodkinm@gmail.com</code> | ||
| + | |||
| + | [https://docs.google.com/spreadsheets/d/1n6EkI7WZkAc9bNBnr4VtqxqOUodPaHn7A81qGjOzulc/edit?usp=sharing Таблица с результатами] | ||
| + | |||
| + | === Вербицкая Екатерина === | ||
| + | |||
| + | Контакты: <code>kajigor@gmail.com</code> | ||
| + | |||
| + | [https://docs.google.com/spreadsheets/d/1n6EkI7WZkAc9bNBnr4VtqxqOUodPaHn7A81qGjOzulc/edit#gid=111213337 Таблица с результатами] | ||
| + | |||
| + | [https://drive.google.com/drive/folders/1yBgcf2yIvxV7NTmm08nWBdu5GcqbeMh5 Домашние задания] | ||
| + | |||
| + | '''Важно''': префикс для темы писем с домашками: <code>[FL_SPbAU] HWxx</code> | ||
Текущая версия на 12:49, 18 июня 2018
Содержание
Лекции
Преподаватель: Дворкин Михаил Эдуардович (mikhail.dvorkin@gmail.com)
Список билетов на экзамене
- Детерминированные конечные автоматы. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
- Правые контексты. Прямое произведение ДКА. Динамическое программирование по ДКА.
- Недетерминированные КА, их соотношение с детерминированными. Распознавание слова НКА. Детерминизация. Эквивалентность ДКА и НКА.
- Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ.
- Лемма о разрастании для ДКА.
- КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Однозначные КС-грамматики.
- Нормальная форма Хомского. Все этапы алгоритма приведения к НФХ.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
- Лемма о разрастании для КС-грамматик.
- Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию. Эквивалентность МП-автоматов и КС-грамматик.
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
- Иерархия Хомского. Регулярные грамматики, эквивалентность ДКА. Неограниченные грамматики, эквивалентность машинам Тьюринга.
- Контекстно-зависимые грамматики, неукорачивающие грамматики. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней.
Ссылки
- Важная книга: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
- neerc.ifmo.ru
- [1]
- [2]
- [3]
- [4]
Практика
Слабодкин Михаил
Контакты: slabodkinm@gmail.com
Вербицкая Екатерина
Контакты: kajigor@gmail.com
Важно: префикс для темы писем с домашками: [FL_SPbAU] HWxx
