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

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

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

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

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