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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Конечные автоматы, регулярные выражения, ...»)
 
Строка 1: Строка 1:
Конечные автоматы, регулярные выражения, ...
+
== Лекция 1 ==
 +
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов]]
 +
*[[Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини]]
 +
*[[Регулярные языки: два определения и их эквивалентность]]
 +
*[[Детерминированные конечные автоматы]]
 +
*[[Недетерминированные конечные автоматы]]
 +
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
 +
 
 +
== Лекция 2 ==
 +
*[[Автоматы с eps-переходами. Eps-замыкание]]
 +
*[[Теорема Клини (совпадение классов автоматных и регулярных языков]]
 +
*[[Эквивалентность состояний ДКА]]
 +
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
 +
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
 +
*[[Замкнутость регулярных языков относительно различных операций]]
 +
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
 +
 
 +
== Лекция 3 ==
 +
*[[Доказательство нерегулярности языков: лемма о разрастании]]
 +
*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]
 +
*[[Решение уравнений в регулярных выражениях]]
 +
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
 +
*[[Контексты и синтаксические моноиды]]

Версия 23:05, 30 сентября 2010

Лекция 1

Лекция 2

Лекция 3

Страницы в категории «Теория формальных языков»

Показано 100 страниц из 100, находящихся в данной категории.