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