Теория формальных языков:Тикеты

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

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

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

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

  7. Недетерминированные конечные автоматы
  8. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
  9. Автоматы с eps-переходами. Eps-замыкание
  10. Теорема Клини (совпадение классов автоматных и регулярных языков)
  11. Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
  12. Минимизация ДКА

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

  18. Доказательство нерегулярности языков: лемма о разрастании
  19. Интерпретация булевых формул с кванторами как игр для двух игроков
  20. Решение уравнений в регулярных выражениях
  21. Замкнутость регулярных языков относительно различных операций
  22. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
  23. Контексты и синтаксические моноиды
  24. Другие автоматы

  25. Локальные автоматы[math] ^\star [/math]
  26. Двусторонний детерминированный конечный автомат[math] ^\star [/math]
  27. Квантовые конечные автоматы[math] ^\star [/math]
  28. Автоматы Мура и Мили[math] ^\star [/math]
  29. Автоматы в современном мире[math] ^\star [/math]