Формальные языки 2MIT осень 1 2018

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

Лекции

Преподаватель: Дворкин М. Э., mikhail.dvorkin@gmail.com

Список вопросов на экзамене

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

Ссылки

Аналогичные курсы в разных университетах:

Практика Палецких

Преподаватель: Палецких Алексей Андреевич, a.paletskikh@gmail.com

Задачи можно сдавать устно вплоть до разбора задачи. Лучше заранее записать/прислать для ускорения процесса

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

Практика Вербицкая