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