Материалы курса теория формальных языков разных лет.
В материалах 2021-2023 годов лекции организованы не в соответствии плану обновлённой версии 2024 года.
Рекомендуемая литература по автоматам: Хопкрофт, Эспарца (см. директория 2023, файл Esparza_autoskript.pdf), а также лекции ИТМО.
Если вы всё-таки решите начать с просмотра индусов - имейте в виду, они кое-что умалчивают или упрощают, поэтому сначала индусы, а потом всё-таки читаем конспекты ИТМО и Хопкрофта.
Вспомогательные ресурсы:
- Классический учебник по теории автоматов и языков (Хопркрофт, и др.)
- On the security of the ping-pong protocols. D.Dolev, S. Even, M. Karp
- Mathematical Foundations of Automata Theory. J.-E. Pin
- A Taste of Rewrite Systems. N.Dershowitz
- Total Termination of Term Rewriting. H.Zantema, M.Ferreira
- ординальный калькулятор + интерактивный прувер в ординальной ФуМА (ВКР Александра Пискунова, ИУ9)
- проверка эквивалентности регулярок
- LL(1)-разбор онлайн (навязывается приоритет разбора)
- LR(0)-разбор онлайн (с добавлением эндмаркера)
- конспекты лекций ИТМО по ТФЯ (тут есть весь минимум вплоть до LL- и LR-языков)
- CYK онлайн
- Лекция Охотина про LL-языки
- Продолжение лекции Охотина
- Статья Волкова про синхронизирующиеся автоматы (http)
- ...а это его же темы курсачей (просто чтобы была возможность сравнить себя с кафедрами теор.инф. провинциальных вузов :) ) - простите, не удержалась
- Анализатор КС-грамматик онлайн (3 в 1: LL(1), LR(0-1), неоднозначность)
- Минимизатор конечных автоматов онлайн
- Интерактивный тестировщик пользовательской КС-грамматики
- fuzz-алгоритм, определяющий неоднозначности в расширенных регулярных выражениях, посредством построения их описания в мультиобразцах (ВКР Юлии Беликовой)
- Быстрое сопоставление с расширенными регулярными выражениями посредством построения MFA и алгебраических преобразований (ВКР Дарьи Исмагиловой)
- Решение регулярных уравнений. Реализация Егора Смирнова (ИУ9)
- GLR-разбор конъюнктивных грамматик Охотина + синтаксически управляемая интерпретация получившегося SPPF (ВКР Ильи Щербакова, ИУ9)
- Конвертер автоматов и регулярок с порождением пошагового описания преобразований в latex (А.Дельман, А.Ильин, Д.Князихин, А.Терентьева, М.Терюха, К.Шевченко и др.)
- Ещё один конвертер, с базовым логированием, но зато в master и без необходимости долгой установки (Ю.Проскурников и компания)
- ГНФ-конвертер КС-грамматик (два алгоритма) (И.Павлов, там ещё унификация по соседству)
- Построение трансформационного моноида по автомату (А.Иванов, там ещё Кнут-Бендикс и кое-что ещё интересное по соседству)
- Порождение PDA по описанию и тестирование принадлежности языку PDA (С.Стафиевский, А.Сайкин, Д.Пашкевич)
- Порождение случайных грамматик в пользовательском синтаксисе (полезно для тестирования) (И.Павлов, П.Константинова)
- Построение коммутативного образа КС-грамматики и его описания в векторах (Ю.Петряев) и другие хорошие лабы
- Построение регулярной аппроксимации КС-грамматики по Мори-Недерхопфу (Е. Матвеев и к, ACHTUNG!, лежит в ветке, а не в main)
- Построение аппроксимации AST и другое (А.Котов)
- Построение SLR-автомата и другое (Б.Степанов)
Анти-Доктор:
- 5 вариант РК1 (дополняется)
- 6 вариант РК2 прошлого года (только одна задача)
- Мегасхема решения задач из второго РК прошлого года (на баллы не смотрим, но сама схема может пригодиться)
Если кто-то знает, где лежат красиво написанные решения задач по ТФЯ какого-либо года, хоть какой-то вариант, я сюда добавлю, для нынешнего и будущих поколений (а возможно, пару вариантов разберу тоже письменно).