Формальные языки 5SE весна 2020

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

Лекции

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

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

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

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

Преподаватель: Вербицкая Екатерина kajigor@gmail.com

Репозиторий с домашними заданиями: [4]

Папка с материалами: [5]

Табличка с результатами проверки домашних заданий (вкладка "Практика Вербицкая"): [6]

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

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