Теория автоматов, формальные языки, регулярные выражения

Бакалавриат 2025/2026

Статус: Курс по выбору (Прикладная математика и информатика)

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 4-й курс, 3 модуль

Охват аудитории: для своего кампуса

Преподаватели: Запрягаев Александр Александрович

Язык: русский

Кредиты: 4

Контактные часы: 40

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

Цель освоения дисциплины

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

Планируемые результаты обучения

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

Содержание учебной дисциплины

Формальные языки. Порождающие грамматики. Основные классы порождающих грамматик. Иерархия Хомского
Конечные автоматы. Теоремы о нормальной форме конечных автоматов. Детерминированные конечные автоматы
Автоматные языки. Булевы операции над автоматными языками
Лемма о накачке. Примеры неавтоматных языков
Синтаксис регулярных выражений. Регулярные выражения и автоматы
Контекстно-свободные грамматики. Приложения в компьютерной лингвистике
Результаты об алгебраической разрешимости и неразрешимости в теории автоматов
Автоматные алгебраические структуры. Характеристика автоматных групп
Древесная автоматность, автоматы Бюхи, автоматные линейные порядки
Арифметики Пресбургера и Бюхи. Теорема Бюхи-Брюйер о связи определимости и автоматности. Теорема Кобхэма-Семёнова. Выразимость в арифметиках Бюхи

Элементы контроля

Проверочные работы
Проводятся из расчёта примерно одной работы на 2 семинара в конце семинарских занятий и посвящены темам лекций и семинаров, пройденных с момента предыдущей проверочной работы.
Письменное домашнее задание
Выдаётся дважды за курс: по грамматикам и по конечным автоматам. Дедлайн первого - до начала лекции 6. Дедлайн второго - до контрольной работы.
Контрольная работа
Проводится во время и в аудитории семинара 9. Разрешено пользоваться написанными от руки собственными конспектами, но не распечатанными материалами и не электронными устройствами. Пересдача по уважительной причине проводится во время экзамена.
Экзамен
Проводится в сессию 3 модуля в формате, идентичном контрольной работе, но вопросы включают не только задачи, но и определения, формулировки и простые доказательства.

Промежуточная аттестация

2025/2026 3rd module
Накопленная оценка = Округление(0,3*проверочные+0,3*домашние задания+0,4*контрольная работа). Округление арифметическое. Если Накопленная оценка >=8, то то студент может получить Накопленную оценку в качестве итоговой оценки, не приходя на экзамен. В противном случае применяется формула: Оценка = 0.7*(Накопленная оценка)+0,3*(Экзамен).

Список литературы

Авторы

Волкова Вера Константиновна

Программа дисциплины