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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Автоматы и регулярные языки == === Регулярные языки и ДКА === #[[Основные определения: алфав...»)
 
м
Строка 1: Строка 1:
 
== Автоматы и регулярные языки ==
 
== Автоматы и регулярные языки ==
 
=== Регулярные языки и ДКА ===
 
=== Регулярные языки и ДКА ===
#[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
+
<ol>
#[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]
+
<li>[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]</li>
#[[Детерминированные конечные автоматы]]
+
<li>[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]</li>
#[[Прямое произведение ДКА]]
+
<li>[[Детерминированные конечные автоматы]]</li>
#[[Простой сопоставитель регулярных выражений]] <tex> \star </tex>
+
<li>[[Прямое произведение ДКА]]</li>
 
+
<li>[[Простой сопоставитель регулярных выражений]] <tex> \star </tex></li>
 
=== НКА ===
 
=== НКА ===
#[[Недетерминированные конечные автоматы]]
+
<li>[[Недетерминированные конечные автоматы]]</li>
#[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
+
<li>[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]</li>
#[[Автоматы с eps-переходами. Eps-замыкание]]
+
<li>[[Автоматы с eps-переходами. Eps-замыкание]]</li>
#[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
+
<li>[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]</li>
#[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
+
<li>[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]</li>
 
=== Минимизация ДКА ===
 
=== Минимизация ДКА ===
#[[Эквивалентность состояний ДКА]]
+
<li>[[Эквивалентность состояний ДКА]]</li>
#[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
+
<li>[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]</li>
#[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
+
<li>[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]</li>
#[[Алгоритм Бржозовского]]<tex> ^\star </tex>
+
<li>[[Алгоритм Бржозовского]]<tex> ^\star </tex></li>
 
=== Свойства конечных автоматов ===
 
=== Свойства конечных автоматов ===
#[[Доказательство нерегулярности языков: лемма о разрастании]]
+
<li>[[Доказательство нерегулярности языков: лемма о разрастании]]</li>
#[[Интерпретация булевых формул с кванторами как игр для двух игроков]]
+
<li>[[Интерпретация булевых формул с кванторами как игр для двух игроков]]</li>
#[[Решение уравнений в регулярных выражениях]]
+
<li>[[Решение уравнений в регулярных выражениях]]</li>
#[[Замкнутость регулярных языков относительно различных операций]]
+
<li>[[Замкнутость регулярных языков относительно различных операций]]</li>
#[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
+
<li>[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]</li>
#[[Контексты и синтаксические моноиды]]
+
<li>[[Контексты и синтаксические моноиды]]</li>
 
=== Другие автоматы ===
 
=== Другие автоматы ===
#[[Локальные автоматы]]<tex> ^\star </tex>
+
<li>[[Локальные автоматы]]<tex> ^\star </tex></li>
#[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex>
+
<li>[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex></li>
#[[Квантовые конечные автоматы]]<tex> ^\star </tex>
+
<li>[[Квантовые конечные автоматы]]<tex> ^\star </tex></li>
#[[Автоматы Мура и Мили]]<tex> ^\star </tex>
+
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
#[[Автоматы в современном мире]]<tex> ^\star </tex>
+
<li>[[Автоматы в современном мире]]<tex> ^\star </tex></li>
 +
</ol>

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

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

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

  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]