Формальные языки, 5 курс, 2 семестр, 2016/17 — различия между версиями
Материал из SEWiki
(Новая страница: «Лектор — Дворкин Михаил Эдуардович Практика — Михаил Слабодкин, Екатерина Вербицкая ==…») |
|||
| (не показано 20 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
| − | Лектор — Дворкин Михаил Эдуардович | + | Лектор — Дворкин Михаил Эдуардович, mikhail.dvorkin@gmail.com |
| − | Практика — Михаил Слабодкин, Екатерина Вербицкая | + | Практика — Михаил Слабодкин (slabodkinm@gmail.com), Екатерина Вербицкая |
== Лекции == | == Лекции == | ||
| + | Лекция 1 | ||
| + | * Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков. | ||
| + | * Детерминированные конечные автоматы. Принятие слова. | ||
| + | * Эквивалентность состояний. Минимизация ДКА. | ||
| + | Лекция 2 | ||
| + | * Правые контексты. | ||
| + | * Эквивалентность ДКА. | ||
| + | * Прямое произведение ДКА. | ||
| + | * Динамическое программирование по ДКА. | ||
| + | Лекция 3 | ||
| + | * Академические регулярные выражения. | ||
| + | * Теорема Клини — эквивалентность КА и АРВ. | ||
| + | Лекция 4 | ||
| + | * Операции над языками. Свойства регулярных языков. | ||
| + | * Лемма о разрастании. | ||
| + | Лекция 5 | ||
| + | * КС-грамматики. | ||
| + | * Вывод, левосторонний вывод, дерево разбора. | ||
| + | * Однозначные КС-грамматики. | ||
| + | * Вложенность регулярных языков в КС-языки. | ||
| + | Лекция 6 | ||
| + | * Нормальная форма Хомского. | ||
| + | * Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | ||
| + | * Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
| + | * Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ. | ||
| + | Лекция 7 | ||
| + | * Лемма о разрастании для КС-грамматик | ||
| + | * Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию | ||
| + | Лекция 8 | ||
| + | * Эквивалентность МП-автоматов и КС-грамматик | ||
| + | * Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема | ||
| + | * Соотношение регулярных, ДМП- и КС-языков | ||
| + | Лекция 9 | ||
| + | * Иерархия Хомского | ||
| + | * Регулярные грамматики, эквивалентность ДКА | ||
| + | * Контекстно-зависимые грамматики, неукорачивающие грамматики | ||
| + | * Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней | ||
| + | * Неограниченные грамматики, эквивалентность машинам Тьюринга | ||
== Практика Слабодкин == | == Практика Слабодкин == | ||
| + | [https://docs.google.com/spreadsheets/d/1zu2aoCWlkwGyPoKVF9TpeHUlbfNNFhrNZ9LLdBsMsf4/edit?usp=sharing Таблица с результатами] | ||
| + | |||
| + | [[Медиа:FL_S_1.pdf|Практика 1]] | ||
| + | |||
| + | [[Медиа:FL_S_2.pdf|Практика 2]] | ||
| + | |||
| + | [[Медиа: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]] | ||
== Практика Вербицкая == | == Практика Вербицкая == | ||
| + | |||
| + | [https://docs.google.com/spreadsheets/d/1lf7Qu2fbR_rFMCQGQeCw4n1tNc683vrxJ0FneZ4uPtI/edit?usp=sharing Таблица с результатами] | ||
| + | |||
| + | [[Медиа:FL_V_1.pdf|Практика 1]] | ||
| + | |||
| + | [[Медиа: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]] | ||
| + | |||
| + | == Ссылки == | ||
| + | |||
| + | * Важная книга: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений. | ||
| + | * [http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков] | ||
| + | * [http://www.ics.uci.edu/~goodrich/teach/cs162/notes/] | ||
| + | * [http://www.eecs.wsu.edu/~ananth/CptS317/] | ||
| + | * [http://users.utu.fi/jkari/automata/fullnotes.pdf] | ||
| + | * [http://yeputons.net/spbau/term4/formal_languages-lectures.pdf] | ||
Текущая версия на 00:08, 18 мая 2017
Лектор — Дворкин Михаил Эдуардович, mikhail.dvorkin@gmail.com
Практика — Михаил Слабодкин (slabodkinm@gmail.com), Екатерина Вербицкая
Содержание
Лекции
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
Лекция 2
- Правые контексты.
- Эквивалентность ДКА.
- Прямое произведение ДКА.
- Динамическое программирование по ДКА.
Лекция 3
- Академические регулярные выражения.
- Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
- Операции над языками. Свойства регулярных языков.
- Лемма о разрастании.
Лекция 5
- КС-грамматики.
- Вывод, левосторонний вывод, дерево разбора.
- Однозначные КС-грамматики.
- Вложенность регулярных языков в КС-языки.
Лекция 6
- Нормальная форма Хомского.
- Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
- Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ.
Лекция 7
- Лемма о разрастании для КС-грамматик
- Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию
Лекция 8
- Эквивалентность МП-автоматов и КС-грамматик
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема
- Соотношение регулярных, ДМП- и КС-языков
Лекция 9
- Иерархия Хомского
- Регулярные грамматики, эквивалентность ДКА
- Контекстно-зависимые грамматики, неукорачивающие грамматики
- Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней
- Неограниченные грамматики, эквивалентность машинам Тьюринга
