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

Spirina.es в 14:23, 29 октября 2026

2026-10-29T14:23:19Z

← Предыдущая версия		Версия от 14:23, 29 октября 2026
Строка 1:		Строка 1:
	== 1. О курсе ==		== О курсе ==

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


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

	* '''Дискретная математика и математическая логика.''' Отношения эквивалентности, индукция, разрешимость и неразрешимость. Неразрешимость мы не доказываем заново, а пользуемся ей.		* '''Дискретная математика и математическая логика.''' Отношения эквивалентности, индукция, разрешимость и неразрешимость. Неразрешимость мы не доказываем заново, а пользуемся ей.
Строка 21:		Строка 21:


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

	К концу семестра студент умеет:		К концу семестра студент умеет:
Строка 31:		Строка 31:
	* Строить конечный преобразователь для заданного преобразования и раскладывать его по теореме Нива.		* Строить конечный преобразователь для заданного преобразования и раскладывать его по теореме Нива.

			== Команда курса ==
			'''Лектор:''' Ахтямов Павел Ибрагимович
			'''Семинаристы:''' Обжерин Евсей Романович
			Горбулев Алексей Ильич
			Шпилевой Денис
			Терехова Ольга Алексеевна
			Накорнеева Юлия Альбертовна
			Сазанович Михаил Дмитриевич
			Спицын Николай Антонович
			Игнатьев Николай Эдуардович

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

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


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

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


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

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


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

	=== Как складывается итоговая оценка ===		=== Как складывается итоговая оценка ===
Строка 213:		Строка 223:


	== 8. Экзамен ==		== Экзамен ==

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


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

	* М. Р. Пентус. ''Математическая теория формальных языков''.		* М. Р. Пентус. ''Математическая теория формальных языков''.

Spirina.es: Новая страница: «== 1. О курсе == Курс отвечает на четыре вопроса, и все они про то, как машина понимает текст: * Как автоматически определять типы слов? * Как автоматически разбирать предложения на слова? * Как разбор связан с машинами Тьюринга? * Как разбор работает в компил...»

2026-08-21T09:57:05Z

Новая страница: «== 1. О курсе == Курс отвечает на четыре вопроса, и все они про то, как машина понимает текст: * Как автоматически определять типы слов? * Как автоматически разбирать предложения на слова? * Как разбор связан с машинами Тьюринга? * Как разбор работает в компил...»

Новая страница

== 1. О курсе ==

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{| class="wikitable"
! № недели
! Лекция
! Семинар
! Домашнее задание
|-
| 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 баллов и есть первая половина итоговой оценки.

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

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

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

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

=== Выбор потока ===

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

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

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

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

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

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

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

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

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

== 8. Экзамен ==

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

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

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