Теория Конечных Автоматов и Формальных Грамматик

"Development I", Escher, 1937

Курс читается для студентов 3го курса факультета ПМ-ПУ, СПбГУ, специальность «Информационные технологии».

Лектор: Иванов Владимир Витальевич

Mailing list: apmath_theory_of_computation

Содержание курса

  1. Регулярные языки [слайды]
    • конечные автоматы (DFA, NFA, ε-NFA)
    • регулярные выражения (RE)
    • свойства регулярных языков
    • эквивалентность и минимизация конечных автоматов
  2. Контекстно-свободные языки (CFL) [слайды, p.1-119]
    • контекстно-свободные грамматики (CFG)
    • типы вывода и деревья разбора
    • неоднозначность в грамматиках и языках
    • недетерминированные конечные автоматы с магазинной памятью (PDA)
    • понятие распознавания для PDA
    • эквивалентность CFG и PDA
    • детерминированныe PDA
    • нормальные формы для CFG
      • нормальная форма Хомского (CNF)
      • нормальная форма Грейбах
    • свойства CFL
    • разрешимые проблемы для класса CFL
    • проблема принадлежности строки CFL
      • алгоритм CYK
  3. Синтаксический анализ [слайды, p.119-174]
    • нисходящий(LL) разбор
    • восходящий(LR) разбор
    • моделирование недетерминированного преобразователя с магазинной памятью
    • детерминированный алгоритм нисходящего разбора с возвратами
    • LL(k) грамматики
  4. Нетипизированное λ-исчисление [слайды, article]
    • λ-выражение
    • эквивалентность и нормализация λ-выражений
    • способы кодирования данных
    • рекурсивность в λ-исчислении
    • SECD-машина
    • комбинаторы и SKI combinator calculus
    • λ-исчисление и основные факты теории вычислений
    • λ-исчисление с простой типизацией
    • изоморфизм Карри-Говарда: связь между формулами и типами
    • типизация по Чёрчу и типизация по Карри
    • наиболее общий тип выражения
    • свойства λ-исчисления с простой типизацией

Практические задачи

  • регулярные языки
    • переход от NFA к DFA
    • переход от ε-NFA к DFA
    • минимизация DFA
    • доказательство нерегулярности языка
  • контекстно-свободные языки
    • переход от CFG к PDA
    • переход от PDA к CFG
    • приведение CFG к CNF
    • определить принадлежность строки языку CFG с помощью алгоритма CYK
    • доказать, что язык не является контекстно-свободным
  • синтаксический анализ
    • нисходящий разбор
    • восходящий разбор
  • λ-исчисление
    • нормализация λ-выражения
    • типизированное λ-исчисление
    • вычисление типа выражения
    • построения выражения заданного типа
    • доказательство утверждения в логике PROP

Примеры

Рекомендуемая литература

Материалы


2010/09/30 14:12 редактировал vi