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