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

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

Лекции

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

Предварительный план лекций

  • Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
  • Детерминированные конечные автоматы. Принятие слова.
  • Эквивалентность состояний. Минимизация ДКА.
  • Правые контексты.
  • Эквивалентность ДКА.
  • Прямое произведение ДКА.
  • Динамическое программирование по ДКА.
  • Академические регулярные выражения.
  • Теорема Клини — эквивалентность КА и АРВ.
  • Операции над языками. Свойства регулярных языков.
  • Лемма о разрастании.
  • КС-грамматики.
  • Вывод, левосторонний вывод, дерево разбора.
  • Однозначные КС-грамматики.
  • Вложенность регулярных языков в КС-языки.
  • Нормальная форма Хомского.
  • Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
  • Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
  • Нормальная форма Грейбах, ослабленная нормальная форма Грейбах, приведение произвольной КС-грамматики к ослабленной НФГ.
  • Лемма о разрастании для КС-грамматик
  • Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию
  • Эквивалентность МП-автоматов и КС-грамматик
  • Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема
  • Соотношение регулярных, ДМП- и КС-языков
  • Иерархия Хомского
  • Регулярные грамматики, эквивалентность ДКА
  • Контекстно-зависимые грамматики, неукорачивающие грамматики
  • Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней
  • Неограниченные грамматики, эквивалентность машинам Тьюринга

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

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

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

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

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

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

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