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

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

Лекции: Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)

Практика: Екатерина Вербицкая, Михаил Слабодкин (slabodkinm@gmail.com).

План

Лекция 1

  • Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
  • Детерминированные конечные автоматы. Принятие слова.
  • Эквивалентность состояний. Минимизация ДКА.

Лекция 2

  • Правые контексты.
  • Эквивалентность ДКА.
  • Прямое произведение ДКА.
  • Динамическое программирование по ДКА.

Лекция 3

  • Академические регулярные выражения.
  • Теорема Клини — эквивалентность КА и АРВ.

Лекция 4

  • Операции над языками. Свойства регулярных языков.
  • Лемма о разрастании.

Лекция 5

  • КС-грамматики.
  • Вывод, левосторонний вывод, дерево разбора.
  • Однозначные КС-грамматики.
  • Вложенность регулярных языков в КС-языки.

Лекция 6

  • Нормальная форма Хомского.
  • Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
  • Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.

Подгруппа Михаила Слабодкина

Результаты

Подгруппа Екатерины Вербицкой

Результаты

Ссылки

  • Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
  • [1]
  • [2]
  • [3]
  • [4]