Содержание
Теория Конечных Автоматов и Формальных Грамматик
Курс читается для студентов 3го курса факультета ПМ-ПУ, СПбГУ, специальность «Информационные технологии».
Лектор: Иванов Владимир Витальевич
Mailing list: apmath_theory_of_computation
Содержание курса
1 Регулярные языки [слайды]
- конечные автоматы (DFA, NFA, ε-NFA)
- регулярные выражения (RE)
- свойства регулярных языков
- эквивалентность и минимизация конечных автоматов
1 Контекстно-свободные языки (CFL) [слайды, p.1-119]
- контекстно-свободные грамматики (CFG)
- типы вывода и деревья разбора
- неоднозначность в грамматиках и языках
- недетерминированные конечные автоматы с магазинной памятью (PDA)
- понятие распознавания для PDA
- эквивалентность CFG и PDA
- детерминированныe PDA
- нормальные формы для CFG
- нормальная форма Хомского (CNF)
- нормальная форма Грейбах
- свойства CFL
- разрешимые проблемы для класса CFL
- проблема принадлежности строки CFL
- алгоритм CYK
1 Синтаксический анализ [слайды, p.119-174]
- нисходящий(LL) разбор
- восходящий(LR) разбор
- моделирование недетерминированного преобразователя с магазинной памятью
- детерминированный алгоритм нисходящего разбора с возвратами
- LL(k) грамматики
1 Нетипизированное λ-исчисление [слайды, article]
- λ-выражение
- эквивалентность и нормализация λ-выражений
- способы кодирования данных
- рекурсивность в λ-исчислении
- SECD-машина
- комбинаторы и SKI combinator calculus
- λ-исчисление и основные факты теории вычислений
1 λ-исчисление с простой типизацией ($ \lambda^{\rightarrow} $) [слайды, article]
- λ-исчисление с простой типизацией
- изоморфизм Карри-Говарда: связь между формулами и типами
- типизация по Чёрчу и типизация по Карри
- наиболее общий тип выражения
- свойства λ-исчисления с простой типизацией
Практические задачи
- регулярные языки
- переход от NFA к DFA
- переход от ε-NFA к DFA
- минимизация DFA
- доказательство нерегулярности языка
- контекстно-свободные языки
- переход от CFG к PDA
- переход от PDA к CFG
- приведение CFG к CNF
- определить принадлежность строки языку CFG с помощью алгоритма CYK
- доказать, что язык не является контекстно-свободным
- синтаксический анализ
- нисходящий разбор
- восходящий разбор
- λ-исчисление
- нормализация λ-выражения
- типизированное λ-исчисление
- вычисление типа выражения
- построения выражения заданного типа
- доказательство утверждения в логике PROP
Рекомендуемая литература
1 Hopcroft, Motwani, Ullman "Introduction to Automata Theory,
Languages, and Computation"
Хопкрофт, Мотвани, Ульман "Введение в теорию автоматов, языков и
вычислений"
1 Sipser, "Introduction to the Theory of Computation"
1 Hofstadter, "Gödel, Escher, Bach: An Eternal Golden Braid"
Хофштадтер "Гедель, Эшер, Бах. Эта бесконечная гирлянда"