Теория автоматов, формальные языки, регулярные выражения (ОП ПМИ 4 курс), весна 2026

Лекции проходят по субботам, 11:10–12:30. Первая лекция – 24 января 2026.

Семинары проходят по субботам, 13:00–14:20. Первый семинар - 24 января 2026.

Аудитория меняется, будет указана в РУЗе.

Контакты

Лектор и семинарист: Запрягаев Александр Александрович, azapryagaev@hse.ru, телеграм: azapryagaev

Группа в Телеграм: https://t.me/+ymCEMU8dmLVkMzJi

Информация

Подробная информация

Аннотация

Курс «Теория автоматов, формальные языки, регулярные выражения» познакомит слушателей одной из самых быстро развивающихся дисциплин теоретической информатики – теорией автоматов. Мы рассмотрим, как язык конечных автоматов применяется в алгебре и компьютерной лингвистике, позволяет исследовать грамматику реальных языков и языков программирования, характеризовать устройство алгебраических структур. Будут доказаны теоремы о выразительной силе формальных языков и алгоритмической разрешимости и неразрешимости различных классов структур, выражающихся автоматами.

Цели освоения курса

Овладеть различными видами формальных грамматик на различных уровнях иерархии Хомского
Познакомиться с основными алгоритмами теории конечных автоматов
Научиться строить регулярные выражения
Уметь распознавать языки, не выразимые грамматиками или автоматами
Знать соответствия между разновидностями автоматов и различными категориями грамматик
Овладеть арифметиками Бюхи как методом проверки структур на автоматность
Изучить основные результаты об автоматности алгебраических структур

Планируемые результаты

Уметь классифицировать формальные языки в соответствии с иерархией Хомского
Составлять грамматики и регулярные выражения, задающие конкретные формальные языки
Доказывать нераспознаваемость языков в грамматиках различного вида
Составлять конечные автоматы, соответствующие грамматикам, и наоборот
Детерминизовывать конечные автоматы
Знать роль арифметик Бюхи в представлении автоматных структур
Проверять автоматность произвольных алгебраических структур построением их представления в арифметиках Бюхи

Пререквизиты курса

Некоторый опыт в работе с математическими доказательствами Знакомство с основными структурами алгебры (группы, кольца, поля), а также с языком логики предикатов полезно, но не обязательно.

Отчётность по курсу и критерии оценки

Проверочные работы: Проводятся из расчёта примерно одной работы на 2 семинара в конце семинарских занятий и посвящены темам лекций и семинаров, пройденных с момента предыдущей проверочной работы.

Решение каждой работы оценивается от 0 до 3 баллов. Итоговая оценка составляет 10*(набранное число баллов/(3*число проверочных работ)).

Письменное домашнее задание: Выдаётся дважды за курс: по грамматикам и по конечным автоматам. Дедлайн первого - до начала лекции 6. Дедлайн второго - до контрольной работы.

У каждой задачи указано количество баллов за неё, суммарное количество >10. Оценка равняется 0,5*min(20,сумма баллов, набранных за все задачи).

Контрольная работа: Проводится во время и в аудитории семинара 9. Разрешено пользоваться написанными от руки собственными конспектами, но не распечатанными материалами и не электронными устройствами. Пересдача по уважительной причине проводится во время экзамена.

Решение каждой задачи оценивается из максимума в 3 балла, до максимума 15 баллов (5 задач). Оценка равняется (2/3)*(баллы за задачи).

Экзамен: Проводится в сессию 3 модуля в формате, идентичном контрольной работе, но вопросы включают не только задачи, но и определения, формулировки и простые доказательства.

Решение каждой задачи оценивается из максимума в 3 балла, до максимума 15 баллов (5 задач). Оценка равняется (2/3)*(баллы за задачи).

Пересдача: Первая пересдача проводится в формате, аналогичном экзамену, и представляет собой пересдачу экзамена. Формула итоговой оценки не меняется. Вторая пересдача (с комиссией) проводится в формате, аналогичном экзамену. Формула оценки не меняется.

Формула оценки и пересдачи

Накопленная оценка = Округление(0,3*проверочные+0,3*домашние задания+0,4*контрольная работа).

Округление арифметическое.

Если Накопленная оценка >=8, то то студент может получить Накопленную оценку в качестве итоговой оценки, не приходя на экзамен.

В противном случае применяется формула:

Оценка = 0.7*(Накопленная оценка)+0,3*(Экзамен).

Прочитанные лекции

Конспект лекций 1–8 и листки домашних заданий 1-2

Лекция 1 (24 января)

Формальные языки. Порождающие грамматики. Основные классы порождающих грамматик.

Лекция 2 (31 января)

Конечные автоматы. Теоремы о нормальной форме конечных автоматов. Детерминированные конечные автоматы.

Лекция 3 (7 февраля)

Автоматные языки. Булевы операции над автоматными языками. Лемма о накачке. Примеры неавтоматных языков.

Лекция 4 (14 февраля)

Синтаксис регулярных выражений. Регулярные выражения и автоматы.

Лекция 5 (21 февраля)

Выводы в контекстно-свободных грамматиках. Однозначные грамматики. Нормальная форма Хомского.

Лекция 6 (28 февраля)

Лемма о накачке для контекстно-свободных языков. Булевы операции над контекстно-свободными языками.

Лекция 7 (5 марта)

Стековые автоматы. Автоматное представление контекстно-свободных языков.

Лекция 8 (7 марта)

Системы соответствий Поста. Неразрешимые проблемы в теории формальных языков.

Лекция 9 (19 марта)

Арифметическое представление автоматных языков. Арифметики Бюхи.

Ведомость

Ведомость курса

Литература

Eilenberg S., Tilson B. Automata, languages, and machines (Vol. A and B). – Нью-Йорк, Лондон: Academic press, 1974.
Пентус А. Е., Пентус М. Р. Теория формальных языков. – М.: Мехмат МГУ, 2004.
Khoussainov B., Nerode A. Automatic presentations of structures //International Workshop on Logic and Computational Complexity. – Berlin, Heidelberg : Springer Berlin Heidelberg, 1994. – С. 367-392.
Bruyère V. et al. Logic and p-recognizable sets of integers //Bulletin of the Belgian Mathematical Society Simon Stevin. – 1994. – Т. 1. – №. 2. – С. 191–238.