Изменения

[[Категория: Теория формальных языков]]

*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов]]

*[[Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини]]

*[[Недетерминированные конечные автоматы]]

*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]

*[[Автоматы с eps-переходами. Eps-замыкание]]

*[[Теорема Клини (совпадение классов автоматных и регулярных языков]]

*[[Замкнутость регулярных языков относительно различных операций]]

*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]

*[[Доказательство нерегулярности языков: лемма о разрастании]]

*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]

*[[Контексты и синтаксические моноиды]]

*[[Формальные грамматики]]

*[[Иерархия Хомского формальных грамматик]]

*[[Удаление длинных правил из грамматики]]

*[[Нормальная форма Хомского]]