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