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

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

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

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

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

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

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

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

  21. Локальные автоматы[math] ^\star [/math]
  22. Двусторонний детерминированный конечный автомат[math] ^\star [/math]
  23. Квантовые конечные автоматы[math] ^\star [/math]
  24. Автоматы Мура и Мили[math] ^\star [/math]
  25. Автоматы в современном мире[math] ^\star [/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков:Тикеты&oldid=60790»