Предисловие. 3
Введение. 5
1. Цепочки, языки и грамматики. 10
1.1. Множества цепочек. 10
1.2. Грамматики составляющих. 12
1.3. Грамматики с ограничениями на правила. 17
Упражнения. 21
2. Регулярные множества и конечные автоматы. 23
2.1. Регулярные множества и выражения. 23
2.2. Конечные автоматы. 25
2.3. Свойства регулярных множеств. 32
2.4. Минимизация конечного автомата. 39
Упражнения. 44
3. Контекстно-свободные языки и магазинные автоматы. 47
3.1. Деревья выводов и однозначность грамматик. 47
3.2. Преобразования КС-грамматик. 49
3.3. Автоматы с магазинной памятью. 59
3.4. Свойства класса КС-языков. 65
Упражнения. 69
4. Сложность алгоритмов и языков. 72
4.1. Машины Тьюринга. 72
4.2. Разрешимые и неразрешимые проблемы. 81
4.3. Классы P и NP. 90
4.4. Моделирование МТ. 95
4.5. Полиномиальная сводимость и NP-полнота. 101
4.6. Методы доказательства NP-полноты. 109
4.7. Существование сколь угодно сложных задач. 121
4.8. Иерархия языков. 124
4.9. Техника следов и сложность распознавания симметрии. 129
Упражнения. 138
5. Сети Петри. 142
5.1. События и условия, определение сети Петри. 142
5.2. Моделирование сетями Петри. 151
5.3. Свойства сетей Петри. 166
Упражнения. 193
Список литературы. 195
Оглавление. 196