Формальные языки, 2 курс, весна 2016 — различия между версиями
Материал из SEWiki
(→Список вопросов) |
|||
(не показано 9 промежуточных версий 3 участников) | |||
Строка 36: | Строка 36: | ||
Лекция 8 | Лекция 8 | ||
* Эквивалентность МП-автоматов и КС-грамматик | * Эквивалентность МП-автоматов и КС-грамматик | ||
− | * | + | * Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема |
* Соотношение регулярных, ДМП- и КС-языков | * Соотношение регулярных, ДМП- и КС-языков | ||
Лекция 9 | Лекция 9 | ||
Строка 44: | Строка 44: | ||
* Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней | * Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней | ||
* Неограниченные грамматики, эквивалентность машинам Тьюринга | * Неограниченные грамматики, эквивалентность машинам Тьюринга | ||
+ | Лекция 10 (правильнее: 6.5) | ||
+ | * Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ. | ||
+ | |||
+ | == Список вопросов == | ||
+ | |||
+ | UPDATE: Билет №14 появился в этом документе позже, заметьте его, пожалуйста. | ||
+ | UPDATE: Билет №15 уточнён. | ||
+ | |||
+ | # Детерминированные конечные автоматы. Определение. Принятие слова. Эквивалентность состояний. Минимизация ДКА. | ||
+ | # Правые контексты. Связь с размером минимального ДКА. Прямое произведение ДКА. Динамическое программирование по ДКА, примеры. | ||
+ | # Недетерминированные конечные автоматы с eps-переходами. Детерминизация НКА. | ||
+ | # Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из КА в АРВ. | ||
+ | # Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из АРВ в КА. | ||
+ | # Лемма о разрастании для регулярных языков. | ||
+ | # КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Вложенность регулярных языков в КС-языки. | ||
+ | # Нормальная форма Хомского. Приведение к ней: удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций. | ||
+ | # Нормальная и ослабленная нормальная форма Грейбах. Приведение к ослабленной НФГ. | ||
+ | # Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами. | ||
+ | # Лемма о разрастании для КС-языков. | ||
+ | # Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из АМП в КСГ. | ||
+ | # Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из КСГ в АМП. | ||
+ | # Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков. | ||
+ | # Иерархия Хомского: уровни, доказательства нестрогой вложенности, примеры, демонстрирующие строгую вложенность (без доказательств). Регулярные грамматики, их эквивалентность регулярным языкам. Контекстно-зависимые грамматики, неукорачивающие грамматики, их эквивалентность. | ||
+ | # Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней | ||
== К занятиям Николая Карпова == | == К занятиям Николая Карпова == | ||
Строка 99: | Строка 123: | ||
!10 | !10 | ||
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkUGlYUEY2NjVxMFE/view На 29.04.2016] | |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] | ||
|} | |} | ||
Текущая версия на 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 |