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