Теория автоматов и формальных грамматик
Общий курс
Составитель: ассистент Иванов В.В.
- Конечные автоматы:
- Детерминированные конечные автоматы(DFA);
- Недетерминированные конечные автоматы(NFA);
- Конечные автоматы с эпсилон-переходами(e-NFA);
- Эквивалентность DFA, NFA и e-NFA;
- Регулярные выражения и языки:
- Регулярные выражения;
- Конечные автоматы и регулярные выражения;
- Свойства регулярных языков;
- Минимизация конечных автоматов;
- Контекстно-свободные грамматики(CFG) и языки:
- Контекстно-свободные грамматики;
- Деревья разбора;
- Нисходящие и восходящие распознаватели;
- LL- и LR-грамматики;
- Свойства контекстно-свободных грамматик;
- Нормальная форма Хомского;
- Автоматы с магазинной памятью(PDA):
- Автоматы с магазинной памятью;
- Языки, допускаемые магазинным автоматом;
- Эквивалентность PDA и CFG;
- Детерминированные автоматы с магазинной памятью(DPA);
- Машина Тьюринга:
- Базовая машина Тьюринга;
- Расширения базовой машины Тьюринга;
- Ограниченные машины Тьюринга;
- Рекурсивные и рекурсивно-перечислимые(RE) языки
- Алгоритмически неразрешимые и трудно разрешимые задачи:
- Алгоритмически неразрешимые задачи;
- P и NP классы сложности;
- NP-полные задачи;
- Дополнительные классы сложности;
- Иерархия грамматик по Хомскому
Список рекомендуемой литературы:
- Ахо А., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2001
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. М.: Мир, 1978
- Братчиков И. Л. Синтаксис языков программирования. М.: Мир, 1975
- Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970
- Гладкий А. В. Формальные грамматики и языки. М.: Наука, 1973
- Гросс М., Лантен А. Теория формальных грамматик. М.: Мир, 1971
- Рейуорд-Смит В. Дж. Теория формальных языков. Вводный курс. М.: Радио и связь, 1988
- Саломаа А. Жемчужины теории формальных языков. М.: Мир, 1986
- Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез). М.: Наука, 1970
- Хопкрофт Дж. Э., Мотвани Р., Ульман Дж. Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002
- J.E. Hopcroft, R. Motwani, J.D. Ullman Introduction to Automata Theory, Languages, and Computation, 1st Edition(1979), 2nd Edition(2001)
- M.D. Davis, R. Sigal, E.J.Weyuker Computability, Complexity and Languages, 1994
- H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation, 2nd Edition, 1997
- M. Sipser Introduction to the Theory of Computation, 1997
- D.C. Kozen Automata and Computability, 1997.
- M.R. Garey, D.S. Johnson Computers and Intractability - A Guide to the Theory of NP-Completeness, 1979.
Ссылки
- Пентус А. Е., Пентус М. Р. - Теория формальных языков: Учебное пособие http://lpcs.math.msu.su/~pentus/tfyaw.htm
- Automata theory overview: http://en.wikipedia.org/wiki/Automata_theory
- Introduction to Theoretical Computer Science Web Course: http://www.cs.odu.edu/~toida/nerzic/390teched/web_course.html
- Formal Languages and Automata Theory Cource Lecture notes: http://courses.cs.vt.edu/~cs4114/lectures/
- Parsing Techniques - A Practical Guide: http://www.cs.vu.nl/~dick/PTAPG.html
- An Introduction to Formal Language Theory: http://www.cis.ksu.edu/~stough/forlan/book-and-slides.html