Модели вычислений

Лектор - профессор Захаров Владимир Анатольевич.

Программа курса

Конечные автоматы и регулярные выражения

1. Конечные автоматы: определения основных понятий. Языки, распознаваемые конечными автоматами. Замкнутость класса автоматных языков относительно операций объединения, пересечения и дополнения.
2. Детерминированные конечные автоматы. Метод детерминизации конечных автоматов.
3. Алгоритм проверки эквивалентности детерминированных конечных автоматов.
4. Минимальные детерминированные конечные автоматы. Алгоритм минимизации детерминированных конечных автоматов.
5. Алгебра регулярных выражений. Примеры тождеств в алгебре регулярных выражений. Регулярные языки.
6. Алгоритм построения регулярного выражения, определяющего язык, распознаваемый заданным конечным автоматом.
7. Алгоритм построения конечного автомата, распознающего язык, определяемый заданным регулярным выражением. Теорема Клини о совпадении класса автоматных языков и класса регулярных языков.

Литература

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. - М.: Мир, 1978. - 612 с.
2. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. - М.: Вильямс, 2001. - 768 с.
3. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. - М.: МЦНМО, 1999. - 176 с.
4. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. - М.: Мир, 1983.
5. Матрос Д.Ш., Поднебесова Г.Б. Теория алгоритмов. - М.: Бином, 2008. - 200 с.
6. Пунтус А.Е., Пентус М.Р. Математическая теория формальных языков. Серия "Основы информатики и математики" - М: Бином, 2006. - 247 с.
7. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972.
8. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. - М.: Вильямс, 2002. - 528 с.