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

1. Карпов Ю. Г. Теория автоматов. – СПб.: Питер, 2002.

2. Мартыненко Б. К. Языки и трансляции. – СПб.: Изд-во С.-Петербургского ун-та, 2001.

3. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. – М.: Изд. дом «Вильямс», 2002.

4. Albert J., Ottmann Th. Automaten, Sprachen und Maschinen für Anwender. B. I. – Wissenschaftsverlag, 1983.

5. Bucher W., Maurer H. Theoretische Grundlagen der Programmiersprachen. B. I. – Wissenschaftsverlag, 1984.

6. Hopcroft J., Ullman J. Introduction to Automata Theory, Languages and Compu­tation. – Addison-Wesley, 1980.

7. Kuich W. Einführung in die Theorie der Informatik. – TWU, Wien, 1993.

8. Kuich W., Salomaa A. Semirings, Automata, Languages. – Springer, 1986.

9. Salomaa A. Formale Sprachen. – Springer, 1978.

10. Salomaa A. Computation and Automata. – Cambridge University Press, 1985.

11. Schöning U. Theoretische Informatik – kurzgefaßt. – Berlin, Spektrum, 1995.

Содержание

Введение	3
1. Грамматики, автоматы и контекстно-свободные языки	4
2. Грамматики, машины Тьюринга и перечислимые языки	20
3. Теория алгоритмов и рекурсивных функций	38
4. Теория сложности	64
5. Упражнения	70
Рекомендуемая литература	90

3