Формальные языки, 2 курс, весна 2016

Материал из SEWiki
Перейти к: навигация, поиск

Лекции: Михаил Эдуардович Дворкин (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 уточнён.

  1. Детерминированные конечные автоматы. Определение. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
  2. Правые контексты. Связь с размером минимального ДКА. Прямое произведение ДКА. Динамическое программирование по ДКА, примеры.
  3. Недетерминированные конечные автоматы с eps-переходами. Детерминизация НКА.
  4. Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из КА в АРВ.
  5. Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из АРВ в КА.
  6. Лемма о разрастании для регулярных языков.
  7. КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Вложенность регулярных языков в КС-языки.
  8. Нормальная форма Хомского. Приведение к ней: удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
  9. Нормальная и ослабленная нормальная форма Грейбах. Приведение к ослабленной НФГ.
  10. Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
  11. Лемма о разрастании для КС-языков.
  12. Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из АМП в КСГ.
  13. Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из КСГ в АМП.
  14. Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
  15. Иерархия Хомского: уровни, доказательства нестрогой вложенности, примеры, демонстрирующие строгую вложенность (без доказательств). Регулярные грамматики, их эквивалентность регулярным языкам. Контекстно-зависимые грамматики, неукорачивающие грамматики, их эквивалентность.
  16. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней

К занятиям Николая Карпова

Все материалы и табличка.

Таблица с результатами

Домашние задания

Осторожно, теоретически могут быть ссылки на старые версии - актуальные ищите в разделе "Все материалы и табличка" выше.

№ Дата
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

К занятиям Михаила Слабодкина

Результаты

Ссылки

  • Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
  • [1]
  • [2]
  • [3]
  • [4]
Источник — «http://mit.spbau.ru/sewiki/index.php?title=Формальные_языки,_2_курс,_весна_2016&oldid=7933»