Оглавление

Предисловие. 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