Теория формальных языков:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Автоматы и регулярные языки == === Регулярные языки и ДКА === #[[Основные определения: алфав...»)
(нет различий)

Версия 15:52, 17 мая 2017

Автоматы и регулярные языки

Регулярные языки и ДКА

  1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
  2. Регулярные языки: два определения и их эквивалентность, регулярные выражения
  3. Детерминированные конечные автоматы
  4. Прямое произведение ДКА
  5. Простой сопоставитель регулярных выражений [math] \star [/math]

НКА

  1. Недетерминированные конечные автоматы
  2. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
  3. Автоматы с eps-переходами. Eps-замыкание
  4. Теорема Клини (совпадение классов автоматных и регулярных языков)
  5. Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

Минимизация ДКА

  1. Эквивалентность состояний ДКА
  2. Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
  3. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
  4. Алгоритм Бржозовского[math] ^\star [/math]

Свойства конечных автоматов

  1. Доказательство нерегулярности языков: лемма о разрастании
  2. Интерпретация булевых формул с кванторами как игр для двух игроков
  3. Решение уравнений в регулярных выражениях
  4. Замкнутость регулярных языков относительно различных операций
  5. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
  6. Контексты и синтаксические моноиды

Другие автоматы

  1. Локальные автоматы[math] ^\star [/math]
  2. Двусторонний детерминированный конечный автомат[math] ^\star [/math]
  3. Квантовые конечные автоматы[math] ^\star [/math]
  4. Автоматы Мура и Мили[math] ^\star [/math]
  5. Автоматы в современном мире[math] ^\star [/math]