zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов » Теория автоматов и формальных грамматик

Теория автоматов и формальных грамматик

Общий курс

Составитель: ассистент Иванов В.В.

  1. Конечные автоматы:
    • Детерминированные конечные автоматы(DFA);
    • Недетерминированные конечные автоматы(NFA);
    • Конечные автоматы с эпсилон-переходами(e-NFA);
    • Эквивалентность DFA, NFA и e-NFA;
  2. Регулярные выражения и языки:
    • Регулярные выражения;
    • Конечные автоматы и регулярные выражения;
    • Свойства регулярных языков;
    • Минимизация конечных автоматов;
  3. Контекстно-свободные грамматики(CFG) и языки:
    • Контекстно-свободные грамматики;
    • Деревья разбора;
    • Нисходящие и восходящие распознаватели;
    • LL- и LR-грамматики;
    • Свойства контекстно-свободных грамматик;
    • Нормальная форма Хомского;
  4. Автоматы с магазинной памятью(PDA):
    • Автоматы с магазинной памятью;
    • Языки, допускаемые магазинным автоматом;
    • Эквивалентность PDA и CFG;
    • Детерминированные автоматы с магазинной памятью(DPA);
  5. Машина Тьюринга:
    • Базовая машина Тьюринга;
    • Расширения базовой машины Тьюринга;
    • Ограниченные машины Тьюринга;
    • Рекурсивные и рекурсивно-перечислимые(RE) языки
  6. Алгоритмически неразрешимые и трудно разрешимые задачи:
    • Алгоритмически неразрешимые задачи;
    • P и NP классы сложности;
    • NP-полные задачи;
    • Дополнительные классы сложности;
  7. Иерархия грамматик по Хомскому

Список рекомендуемой литературы:

  1. Ахо А., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2001
  2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. М.: Мир, 1978
  3. Братчиков И. Л. Синтаксис языков программирования. М.: Мир, 1975
  4. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970
  5. Гладкий А. В. Формальные грамматики и языки. М.: Наука, 1973
  6. Гросс М., Лантен А. Теория формальных грамматик. М.: Мир, 1971
  7. Рейуорд-Смит В. Дж. Теория формальных языков. Вводный курс. М.: Радио и связь, 1988
  8. Саломаа А. Жемчужины теории формальных языков. М.: Мир, 1986
  9. Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез). М.: Наука, 1970
  10. Хопкрофт Дж. Э., Мотвани Р., Ульман Дж. Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002
  11. J.E. Hopcroft, R. Motwani, J.D. Ullman Introduction to Automata Theory, Languages, and Computation, 1st Edition(1979), 2nd Edition(2001)
  12. M.D. Davis, R. Sigal, E.J.Weyuker Computability, Complexity and Languages, 1994
  13. H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation, 2nd Edition, 1997
  14. M. Sipser Introduction to the Theory of Computation, 1997
  15. D.C. Kozen Automata and Computability, 1997.
  16. M.R. Garey, D.S. Johnson Computers and Intractability - A Guide to the Theory of NP-Completeness, 1979.

Ссылки