6 ПОСТРОЕНИЕ И АНАЛИЗ ЭФФЕКТИВНЫХ АЛГОРИТМОВ 133
6.1 Типы рекурсивных алгоритмов . . . . . . . . . . . . . . . . . . . . . 133
6.2 Устранение рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.3 Методы отсечения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.4 Динамическое программирование . . . . . . . . . . . . . . . . . . . 150
6.4.1 Понятие динамического программирования . . . . . . . . 150
6.4.2 Многоуровневые динамические массивы . . . . . . . . . . 153
6.5 Виртуальные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.6 Эффективные алгоритмы на графах . . . . . . . . . . . . . . . . 160
6.7 Производящие функции . . . . . . . . . . . . . . . . . . . . . . . . . 169
6.8 Контрольные вопросы к разделу . . . . . . . . . . . . . . . . . . . 175
6.9 Упражнения к разделу . . . . . . . . . . . . . . . . . . . . . . . . . . 175
6.9.1 Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
6.9.2 Варианты заданий . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.10 Тесты для самоконтроля к разделу . . . . . . . . . . . . . . . . . . 186
7 ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ 188
7.1 Понятие порождающей грамматики и языка . . . . . . . . . . . 188
7.2 Классификация грамматик . . . . . . . . . . . . . . . . . . . . . . . . 190
7.3 Основные свойства КС–языков и КС–грамматик . . . . . . . . . 191
7.4 Грамматический разбор . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.5 Преобразования КС–грамматик . . . . . . . . . . . . . . . . . . . . 199
7.5.1 Преобразование 1 — правила с одним нетерминалом . . . 199
7.5.2 Преобразование 2 — правила с одинаковыми правыми
частями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
7.5.3 Преобразование 3 — неукорачивающие грамматики . . . 203
7.5.4 Преобразование 4 — непродуктивные нетерминалы . . . 205
7.5.5 Преобразование 5 — независимые нетерминалы . . . . . . 206
7.5.6 Преобразование 6 — терминальные правила . . . . . . . . 207
7.5.7 Преобразования 7 и 8 — леворекурсивные и праворе-
курсивные правила . . . . . . . . . . . . . . . . . . . . . . . . . 208
7.6 Теорема о языке a
n
b
n
c
n
. . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.7 Контрольные вопросы к разделу . . . . . . . . . . . . . . . . . . . 210
7.8 Упражнения к разделу . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7.8.1 Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7.8.2 Варианты заданий . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.9 Тесты для самоконтроля к разделу . . . . . . . . . . . . . . . . . . 214
8 ЯЗЫКИ И АВТОМАТЫ 216
8.1 Понятие автомата и типы автоматов . . . . . . . . . . . . . . . . . 216
8.2 Формальное определение автомата . . . . . . . . . . . . . . . . . . 218
8.3 Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
8.4 Регулярные множества . . . . . . . . . . . . . . . . . . . . . . . . . . 221
8.5 Минимизация конечных автоматов . . . . . . . . . . . . . . . . . . 223
8.6 Операции над регулярными языками . . . . . . . . . . . . . . . . 225
8.7 Автоматные грамматики и конечные автоматы . . . . . . . . . . 229
8.8 Автоматы с магазинной памятью и КС–языки . . . . . . . . . . . 234
8.9 Разбор с возвратом . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
8.10 Контрольные вопросы к разделу . . . . . . . . . . . . . . . . . . . 241
8.11 Упражнения к разделу . . . . . . . . . . . . . . . . . . . . . . . . . . 242
276