Формальные языки и трансляции 2026

1. О курсе

Курс отвечает на четыре вопроса, и все они про то, как машина понимает текст:

• Как автоматически определять типы слов?
• Как автоматически разбирать предложения на слова?
• Как разбор связан с машинами Тьюринга?
• Как разбор работает в компиляторах?

За семестр мы проходим путь от конечного автомата до промышленного алгоритма синтаксического анализа. Сначала разбираемся с регулярными языками и доказываем, что автоматы и регулярные выражения задают одно и то же. Затем поднимаемся по иерархии Хомского к контекстно-свободным грамматикам и учимся строить по ним разбор за полиномиальное время. Заканчиваем LR-анализом, который лежит внутри реальных компиляторов, и конечными преобразователями, через которые описывается контекстная замена.

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

2. Пререквизиты

• Дискретная математика и математическая логика. Отношения эквивалентности, индукция, разрешимость и неразрешимость. Неразрешимость мы не доказываем заново, а пользуемся ей.
• Алгебра. Понятие моноида и подмоноида приходит из теории групп, здесь оно применяется к языкам.
• Алгоритмы и структуры данных. Обходы графов, динамическое программирование, оценка асимптотики.
• Программирование на любом языке, если выбирается практический вариант отчётности.

3. Результаты обучения

К концу семестра студент умеет:

• Строить конечный автомат по регулярному выражению и обратно, минимизировать автомат и доказывать, что он минимальный.
• Доказывать, что язык не является автоматным или не является контекстно-свободным, причём тремя разными способами: леммой о разрастании, теоремой Майхилла и Нероуда и замкнутостью относительно операций.
• Приводить грамматику к нормальным формам Хомского и Грейбах и понимать, зачем нужна каждая.
• Разбирать слово по грамматике алгоритмами Кока, Янгера и Касами, Эрли и LR(k), оценивая стоимость каждого.
• Строить конечный преобразователь для заданного преобразования и раскладывать его по теореме Нива.

4. Как устроены занятия

Семестр идёт 15 недель. Каждая неделя состоит из одной лекции и одного семинара, оба занятия по два академических часа, то есть по час двадцать.

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

Домашние задания выдаются примерно раз в две недели и написаны сюжетом: орочья война, кобольды с драконом, Великая Библиотека Грамматик. Формулировки от этого не становятся проще, зато условие запоминается.

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

Семестр рассчитан на 15 недель. Темы восстановлены по материалам потока 2025 года, контрольные стоят на неделях 6 и 15.

№ недели	Лекция	Семинар	Домашнее задание
1	НКА, конфигурации, упрощения автомата	Регулярные выражения	ДЗ 1. Регулярные языки
2	Удаление ε-переходов, распознавание слова, переход к ДКА	Конечные автоматы	ДЗ 2. Автоматы и ε-переходы
3	Построение ДКА, замкнутость, теорема Клини	Построение ДКА, теорема Клини	ДЗ 3. Детерминизация и дополнение
4	Лемма о разрастании, эквивалентность слов, классы Σ*/∼	Теорема Клини, лемма о разрастании, минимизация
5	Единственность и построение МПДКА, Майхилл и Нероуд	Лемма о разрастании, эквивалентность языков	ДЗ 4. Минимизация, Майхилл и Нероуд
6	Иерархия Хомского, деревья вывода, однозначность	Контрольная 1 (весь семинар)
7	Форма Хомского, CYK, разрастание	Контекстно-свободные грамматики	ДЗ 5. Грамматики и иерархия Хомского
8	Автоматы с магазинной памятью, эквивалентность с КС-грамматиками	Форма Хомского, CYK, разрастание	ДЗ 6. Нормальная форма Хомского и CYK
9	Алгоритм Эрли: ситуации, корректность, сложность	МП-автоматы	ДЗ 7. МП-автоматы
10	Форма Грейбах, пересечение с регулярным языком	Алгоритм Эрли
11	LR(k): восходящий разбор, активные префиксы, LR(k)-ситуации	Лемма Огдена, перенос-свёртка
12	LR(k): построение таблиц, критерий класса	LR(k)-разбор	ДЗ 8. LR(k)-грамматики
13	LR(k): корректность разбора и линейность	Преобразователи, контекстная замена
14	Преобразователи: определение и примеры	Лемма о накачке, теорема Хомского и Шютценберже	ДЗ 9. Преобразователи, лемма о накачке
15	Композиция, теорема Нива, замкнутость КС-языков	Контрольная 2 (весь семинар)

Контрольная работа занимает семинар целиком, поэтому на неделях 6 и 15 семинарской темы нет. Отсюда общий сдвиг: начиная с седьмой недели семинар отрабатывает материал предыдущей лекции, и для этого курса так даже лучше, потому что между доказательством и задачами появляется пауза.

Контрольная 1 закрывает автоматный блок: регулярные выражения, построение и минимизацию автомата, доказательство неавтоматности.

Контрольная 2 проходит на последней неделе и закрывает контекстно-свободный блок вместе с алгоритмами разбора.

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

6. Дополнительные темы для сильных групп

Часть материала разбирается только там, где группа успевает. В программе он помечен как дополнительный, на экзамене такие темы встречаются в задачах старших уровней:

• Лемма Огдена и доказательство существенной неоднозначности языков (семинар 9).
• Теорема Париха, полулинейные множества и следствие про однобуквенный алфавит (дополнительный семинар).
• Теорема Хомского и Шютценберже в слабой и сильной формах через язык Дика (семинары 12 и 13).
• Индексированные грамматики как взгляд за пределы иерархии.

7. Оценивание

Как складывается итоговая оценка

Итог делится ровно пополам между работой в семестре и экзаменом. Первую половину набирают контрольные, домашние задания и отчётность по выбранному потоку, вторую даёт устный экзамен.

Экзамен блокирующий. Семестровые баллы не компенсируют его провал, каким бы высоким ни был их запас. Смысл такого правила простой: курс проверяет умение доказывать, а доказательство защищается в разговоре, а не накапливается баллами.

Баллы за семестр

Максимум за семестр составляет 50 баллов, и эти 50 баллов и есть первая половина итоговой оценки.

Составляющая	Баллы	Когда
Контрольная работа 1	10	Неделя 6, весь семинар
Контрольная работа 2	10	Неделя 15, весь семинар
Сдача домашних заданий	10	Девять заданий за семестр
Активность на семинарах	До 3 бонусных	В течение семестра

Оставшиеся 25 баллов зависят от выбранного потока.

Теоретический поток сдаёт коллоквиум на 10 баллов и делает доклад на 10 баллов. В этом году коллоквиум проводится только здесь.

Практический поток делает практикум на 10 баллов, реализуя изученные в курсе алгоритмы, и защищает его устно ещё на 10 баллов. Устная защита практикума заменяет коллоквиум: разговор с преподавателем происходит в обоих потоках, просто в одном он идёт про доказательство сложного факта, а в другом про собственный код.

Выбор потока

Решение принимается до середины октября. Время на выбор даётся специально: сначала мы пробуем и то и другое, а потом каждый решает, что ему ближе. Раньше середины октября выбирать не нужно, а после этого срока поток менять уже поздно, потому что подготовка доклада и написание практикума занимают остаток семестра.

Разница между потоками не в сложности, а в характере работы. Теоретический поток ближе тем, кому нравится разбираться в доказательствах и рассказывать их; практический подойдёт тем, кто хочет увидеть, как изученные алгоритмы ведут себя на реальном входе.

Контрольные работы

Каждая контрольная занимает семинар целиком.

Первая проверяет автоматный блок: построение и минимизацию автомата, переход между автоматами и регулярными выражениями, доказательство неавтоматности языка.

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

Домашние задания

За семестр выдаётся девять заданий. Первые три идут еженедельно, пока в курсе автоматный блок с короткими формулировками, дальше задания выдаются раз в две недели.

Задачи внутри задания оцениваются отдельно, и вес задачи указан в условии.

8. Экзамен

Экзамен устный. Структура экзамена будет известна позднее.

9. Литература

• М. Р. Пентус. Математическая теория формальных языков.
• А. Ахо, Д. Ульман. Теория синтаксического анализа, перевода и компиляции, том 1. Основной источник для блока про LR-разбор, нумерация теорем в лекциях 11–13 идёт по этой книге.
• А. Ахо, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии и инструменты (Dragon Book).
• В. Пырэу, Н. Ефанов. Формальные языки (черновик).