Формальные языки, 2 курс, весна 2016 — различия между версиями
Материал из SEWiki
(Новая страница: «'''Лекции:''' Михаил Эдуардович Дворкин '''Практика:''' Николай Карпов (I подгруппа), Михаил С…») |
(→Список вопросов) |
||
(не показана 21 промежуточная версия 5 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Лекции:''' Михаил Эдуардович Дворкин | + | '''Лекции:''' Михаил Эдуардович Дворкин (<b>mikhail.dvorkin@gmail.com</b>) |
− | '''Практика:''' Николай Карпов (I подгруппа), Михаил Слабодкин (II подгруппа). | + | '''Практика:''' Николай Карпов (I подгруппа), Михаил Слабодкин (slabodkinm@gmail.com) (II подгруппа). |
+ | |||
+ | Конспект http://yeputons.net/spbau/term4-formal_languages-lectures.pdf | ||
+ | |||
+ | == План == | ||
+ | |||
+ | Лекция 1 | ||
+ | * Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков. | ||
+ | * Детерминированные конечные автоматы. Принятие слова. | ||
+ | * Эквивалентность состояний. Минимизация ДКА. | ||
+ | Лекция 2 | ||
+ | * Правые контексты. | ||
+ | * Эквивалентность ДКА. | ||
+ | * Прямое произведение ДКА. | ||
+ | * Динамическое программирование по ДКА. | ||
+ | Лекция 3 | ||
+ | * Академические регулярные выражения. | ||
+ | * Теорема Клини — эквивалентность КА и АРВ. | ||
+ | Лекция 4 | ||
+ | * Операции над языками. Свойства регулярных языков. | ||
+ | * Лемма о разрастании. | ||
+ | Лекция 5 | ||
+ | * КС-грамматики. | ||
+ | * Вывод, левосторонний вывод, дерево разбора. | ||
+ | * Однозначные КС-грамматики. | ||
+ | * Вложенность регулярных языков в КС-языки. | ||
+ | Лекция 6 | ||
+ | * Нормальная форма Хомского. | ||
+ | * Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | ||
+ | * Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
+ | Лекция 7 | ||
+ | * Лемма о разрастании для КС-грамматик | ||
+ | * Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию | ||
+ | Лекция 8 | ||
+ | * Эквивалентность МП-автоматов и КС-грамматик | ||
+ | * Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема | ||
+ | * Соотношение регулярных, ДМП- и КС-языков | ||
+ | Лекция 9 | ||
+ | * Иерархия Хомского | ||
+ | * Регулярные грамматики, эквивалентность ДКА | ||
+ | * Контекстно-зависимые грамматики, неукорачивающие грамматики | ||
+ | * Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней | ||
+ | * Неограниченные грамматики, эквивалентность машинам Тьюринга | ||
+ | Лекция 10 (правильнее: 6.5) | ||
+ | * Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ. | ||
+ | |||
+ | == Список вопросов == | ||
+ | |||
+ | UPDATE: Билет №14 появился в этом документе позже, заметьте его, пожалуйста. | ||
+ | UPDATE: Билет №15 уточнён. | ||
+ | |||
+ | # Детерминированные конечные автоматы. Определение. Принятие слова. Эквивалентность состояний. Минимизация ДКА. | ||
+ | # Правые контексты. Связь с размером минимального ДКА. Прямое произведение ДКА. Динамическое программирование по ДКА, примеры. | ||
+ | # Недетерминированные конечные автоматы с eps-переходами. Детерминизация НКА. | ||
+ | # Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из КА в АРВ. | ||
+ | # Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из АРВ в КА. | ||
+ | # Лемма о разрастании для регулярных языков. | ||
+ | # КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Вложенность регулярных языков в КС-языки. | ||
+ | # Нормальная форма Хомского. Приведение к ней: удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | ||
+ | # Нормальная и ослабленная нормальная форма Грейбах. Приведение к ослабленной НФГ. | ||
+ | # Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
+ | # Лемма о разрастании для КС-языков. | ||
+ | # Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из АМП в КСГ. | ||
+ | # Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из КСГ в АМП. | ||
+ | # Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков. | ||
+ | # Иерархия Хомского: уровни, доказательства нестрогой вложенности, примеры, демонстрирующие строгую вложенность (без доказательств). Регулярные грамматики, их эквивалентность регулярным языкам. Контекстно-зависимые грамматики, неукорачивающие грамматики, их эквивалентность. | ||
+ | # Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней | ||
== К занятиям Николая Карпова == | == К занятиям Николая Карпова == | ||
− | [https://drive.google.com/folderview?id=0B9NF86zbFMKkQlBDUHpLZDI0eHM&usp=sharing | + | [https://drive.google.com/folderview?id=0B9NF86zbFMKkQlBDUHpLZDI0eHM&usp=sharing Все материалы и табличка]. |
+ | |||
+ | [https://docs.google.com/spreadsheets/d/1_JhH9h8_k57iw3BEFnlMmK3sfSITwDWVOvlerSA5Wlk/edit?usp=drive_web Таблица с результатами] | ||
+ | |||
+ | === Домашние задания === | ||
+ | Осторожно, теоретически могут быть ссылки на старые версии - актуальные ищите в разделе "Все материалы и табличка" выше. | ||
+ | |||
+ | {| border="1" cellspacing="0" cellpadding="3" | ||
+ | |||
+ | |- | ||
+ | !№ | ||
+ | !Дата | ||
+ | |||
+ | |- | ||
+ | !1 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkMzRQQ09uQmVsbWc/view На 19.02.2016] | ||
+ | |||
+ | |- | ||
+ | !2 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkWXA5UnE2Xy1uczQ/view На 26.02.2016] | ||
+ | |||
+ | |- | ||
+ | !3 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkZy1QY3dVZEhXbzg/view На 04.03.2016] | ||
+ | |||
+ | |- | ||
+ | !4 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkQkl1cUZuZ0FGUm8/view На 11.03.2016] | ||
+ | |||
+ | |- | ||
+ | !5 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkMFBKQmJBa25BYTQ/view На 18.03.2016] | ||
+ | |||
+ | |- | ||
+ | !6 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkZEFUMjRrVVRBTms/view На 25.03.2016] | ||
+ | |||
+ | |- | ||
+ | !7 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkaEVFZ2JxazY4bkE/view На 01.04.2016] | ||
+ | |||
+ | |- | ||
+ | !8 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkeDF1TFRDSktuUW8/view На 08.04.2016] | ||
+ | |||
+ | |- | ||
+ | !9 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkWUJ5YTBOb2RoYzQ/view На 22.04.2016] | ||
+ | |||
+ | |- | ||
+ | !10 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkUGlYUEY2NjVxMFE/view На 29.04.2016] | ||
+ | |||
+ | |- | ||
+ | !11 | ||
+ | |align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkc2wwa2JReU5ranM/view На 06.05.2016] | ||
+ | |} | ||
+ | |||
+ | == К занятиям Михаила Слабодкина == | ||
+ | |||
+ | [https://docs.google.com/spreadsheets/d/13ELlUZn098B5opdQrn1UWfMmDbwosVZ5vKNX7NZDGc8/edit Результаты] | ||
+ | |||
+ | == Ссылки == | ||
+ | |||
+ | * Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений. | ||
+ | * [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] |
Текущая версия на 21:49, 6 июня 2016
Лекции: Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)
Практика: Николай Карпов (I подгруппа), Михаил Слабодкин (slabodkinm@gmail.com) (II подгруппа).
Конспект http://yeputons.net/spbau/term4-formal_languages-lectures.pdf
Содержание
План
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
Лекция 2
- Правые контексты.
- Эквивалентность ДКА.
- Прямое произведение ДКА.
- Динамическое программирование по ДКА.
Лекция 3
- Академические регулярные выражения.
- Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
- Операции над языками. Свойства регулярных языков.
- Лемма о разрастании.
Лекция 5
- КС-грамматики.
- Вывод, левосторонний вывод, дерево разбора.
- Однозначные КС-грамматики.
- Вложенность регулярных языков в КС-языки.
Лекция 6
- Нормальная форма Хомского.
- Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
Лекция 7
- Лемма о разрастании для КС-грамматик
- Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию
Лекция 8
- Эквивалентность МП-автоматов и КС-грамматик
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема
- Соотношение регулярных, ДМП- и КС-языков
Лекция 9
- Иерархия Хомского
- Регулярные грамматики, эквивалентность ДКА
- Контекстно-зависимые грамматики, неукорачивающие грамматики
- Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней
- Неограниченные грамматики, эквивалентность машинам Тьюринга
Лекция 10 (правильнее: 6.5)
- Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ.
Список вопросов
UPDATE: Билет №14 появился в этом документе позже, заметьте его, пожалуйста. UPDATE: Билет №15 уточнён.
- Детерминированные конечные автоматы. Определение. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
- Правые контексты. Связь с размером минимального ДКА. Прямое произведение ДКА. Динамическое программирование по ДКА, примеры.
- Недетерминированные конечные автоматы с eps-переходами. Детерминизация НКА.
- Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из КА в АРВ.
- Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из АРВ в КА.
- Лемма о разрастании для регулярных языков.
- КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Вложенность регулярных языков в КС-языки.
- Нормальная форма Хомского. Приведение к ней: удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Нормальная и ослабленная нормальная форма Грейбах. Приведение к ослабленной НФГ.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
- Лемма о разрастании для КС-языков.
- Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из АМП в КСГ.
- Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из КСГ в АМП.
- Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
- Иерархия Хомского: уровни, доказательства нестрогой вложенности, примеры, демонстрирующие строгую вложенность (без доказательств). Регулярные грамматики, их эквивалентность регулярным языкам. Контекстно-зависимые грамматики, неукорачивающие грамматики, их эквивалентность.
- Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней
К занятиям Николая Карпова
Домашние задания
Осторожно, теоретически могут быть ссылки на старые версии - актуальные ищите в разделе "Все материалы и табличка" выше.
№ | Дата |
---|---|
1 | На 19.02.2016 |
2 | На 26.02.2016 |
3 | На 04.03.2016 |
4 | На 11.03.2016 |
5 | На 18.03.2016 |
6 | На 25.03.2016 |
7 | На 01.04.2016 |
8 | На 08.04.2016 |
9 | На 22.04.2016 |
10 | На 29.04.2016 |
11 | На 06.05.2016 |