|
|
|
|
|
|
|
Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д.
Введение в
теорию автоматов, языков и
вычислений М.:
Издательский дом "Вильямс", 2002 |
|
|
|
|
Содержание |
|
|
|
|
Предисловие Как
пользоваться книгой Требования
к уровню подготовки Упражнения Поддержка
в World Wide Web Благодарности |
14 15 15 16 16 16 |
|
|
|
ГЛАВА 1. Автоматы: методы
и понятия 1.1. Зачем
изучается теория автоматов? 1.1.1.
Введение в теорию конечных автоматов 1.1.2.
Структурные представления 1.1.3.
Автоматы и сложность 1.2. Введение
в теорию формальных доказательств 1.2.1.
Дедуктивные доказательства 1.2.2.
Сведение к определениям 1.2.3.
Другие формы теорем 1.2.4.
Теоремы без гипотезы 1.3. Дополнительные
схемы доказательств 1.3.1.
Доказательства эквивалентностей, связанных с множествами 1.3.2.
Контрапозиция 1.3.3.
Доказательство методом "от противного" 1.3.4.
Контрпримеры 1.4. Индуктивные
доказательства 1.4.1.
Индукция по целым числам 1.4.2.
Более общие формы целочисленных индуктивных доказательств 1.4.3.
Структурная индукция 1.4.4.
Совместная индукция 1.5. Основные
понятия теории автоматов 1.5.1.
Алфавиты 1.5.2.
Цепочки 1.5.3.
Языки 1.5.4.
Проблемы Резюме Литература |
17 18 18 20 21 21 22 25 27 30 30 30 32 34 34 36 36 39 40 43 45 46 46 47 48 50 52 |
|
|
|
ГЛАВА 2. Конечные
автоматы 2.1. Неформальное
знакомство с конечными автоматами 2.1.1.
Основные правила 2.1.2.
Протокол 2.1.3.
Возможность игнорирования автоматом некоторых действий 2.1.4.
Система в целом как автомат 2.1.5.
Проверка протокола с помощью автомата-произведения 2.2. Детерминированные
конечные автоматы 2.2.1.
Определение детерминированного конечного автомата 2.2.2.
Как ДКА обрабатывает цепочки 2.2.3.
Более простые представления ДКА 2.2.4.
Расширение функции переходов на цепочки 2.2.5.
Язык ДКА 2.2.6.
Упражнения к разделу 2.2 2.3. Недетерминированные
конечные автоматы 2.3.1.
Неформальное описание недетерминированного конечного автомата 2.3.2.Определение
недетерминированного конечного автомата 2.3.3.
Расширенная функция переходов 2.3.4.
Язык НКА 2.3.5.
Эквивалентность детерминированных и
недетерминированных конечных
автоматов 2.3.6.
Плохой случай для конструкции подмножеств 2.3.7.
Упражнения к разделу 2.3 2.4. Приложение:
поиск в тексте 2.4.1.
Поиск цепочек в тексте 2.4.2.
Недетерминированные конечные автоматы для поиска в тексте 2.4.3.
ДКА, распознающий множество ключевых слов 2.4.4.
Упражнения к разделу 2.4 2.5. Конечные
автоматы с эпсилон-переходами 2.5.1.
Использование е-переходов 2.5.2.
Формальная запись е-НКА 2.5.3.
Что такое е-замыкание 2.5.4.
Расширенные переходы и языки г-НКА 2.5.5.
Устранение е-переходов 2.5.6.
Упражнения к разделу 2.5 Резюме Литература |
53 54 54 55 57 59 61 61 62 62 64 65 68 69 71 72 73 74 75 77 81 83 85 85 86 87 89 89 89 91 91 92 94 97 97 98 |
|
|
|
ГЛАВА 3. Регулярные
выражения и языки 3.1. Регулярные
выражения 3.1.1.
Операторы регулярных выражений 3.1.2.
Построение регулярных выражений 3.1.3.
Приоритеты регулярных операторов 3.1.4.
Упражнения к разделу 3.1 3.2. Конечные
автоматы и регулярные выражения 3.2.1.
От ДКА к регулярным выражениям 3.2.2.
Преобразование ДКА в регулярное выражение методом исключения
состояний 3.2.3.
Преобразование регулярного выражения в автомат 3.2.4.
Упражнения к разделу 3.2 3.3. Применение
регулярных выражений 3.3.1.
Регулярные выражения в UNIX 3.3.2.
Лексический анализ 3.3.3.
Поиск образцов в тексте 3.3.4.
Упражнения к разделу 3.3 3.4. Алгебраические законы
для регулярных выражений 3.4.1.
Ассоциативность и коммутативность 3.4.2.
Единичные и нулевые элементы 3.4.3.
Дистрибутивные законы 3.4.4.
Закон идемпотентности 3.4.5.
Законы, связанные с оператором итерации 3.4.6.
Установление законов для регулярных выражений 3.4.7. Проверка истинности алгебраических законов для регулярных выражений 3.4.8. Упражнения к разделу 3.4 Резюме Литература |
101 101 102 104 106 108 108 109 114 120 124 126 126 128 130 132 132 133 134 134 135 136 136 139 140 141 142 |
|
|
|
ГЛАВА 4. Свойства
регулярных языков 4.1. Доказательство
нерегулярности языков 4.1.1.
Лемма о накачке для регулярных языков 4.1.2.
Применение леммы о накачке 4.1.3.
Упражнения к разделу 4.1 4.2. Свойства
замкнутости регулярных языков 4.2.1.
Замкнутость регулярных языков относительно булевых операций 4.2.2.
Обращение 4.2.3.
Гомоморфизмы 4.2.4.
Обратный гомоморфизм 4.2.5.
Упражнения к разделу 4.2 4.3. Свойства
разрешимости регулярных языков 4.3.1.
Преобразования различных представлений языков 4.3.2.
Проверка пустоты регулярных языков 4.3.3.
Проверка принадлежности регулярному языку 4.3.4.
Упражнения к разделу 4.3 4.4. Эквивалентность
и минимизация автоматов 4.4.1.
Проверка эквивалентности состояний 4.4.2.
Проверка эквивалентности регулярных языков 4.4.3.
Минимизация ДКА 4.4.4.
Почему минимизированный ДКА невозможно улучшить 4.4.5.
Упражнения к разделу 4.4 Резюме Литература |
143 143 144 145 147 148 149 154 156 157 163 166 167 169 170 171 171 172 175 177 180 182 183 183 |
|
|
|
ГЛАВА 5.
Контекстно-свободные грамматики и языки
5.1. Контекстно-свободные
грамматики 5.1.1.
Неформальный пример 5.1.2.
Определение контекстно-свободных грамматик 5.1.3.
Порождения с использованием грамматики 5.1.4.
Левые и правые порождения 5.1.5.
Язык, задаваемый грамматикой 5.1.6.
Выводимые цепочки 5.1.7.
Упражнения к разделу 5.1 5.2. Деревья
разбора 5.2.1.
Построение деревьев разбора 5.2.2.
Крона дерева разбора 5.2.3.
Вывод, порождение и деревья разбора 5.2.4.
От выводов к деревьям разбора 5.2.5.
От деревьев к порождениям 5.2.6.
От порождений к рекурсивным выводам 5.2.7.
Упражнения к разделу 5.2 5.3. Приложения
контекстно-свободных грамматик 5.3.1.
Синтаксические анализаторы 5.3.2.
Генератор синтаксических анализаторов YACC 5.3.1.
Языки описания документов 5.3.4.
XML и определения типа документа 5.3.5.
Упражнения к разделу 5.3 5.4. Неоднозначность
в грамматиках и языках 5.4.1.
Неоднозначные грамматики 5.4.2.
Исключение неоднозначности из грамматик 5.4.3.
Левые порождения как способ выражения неоднозначности 5.4.4.
Существенная неоднозначность 5.4.5.
Упражнения к разделу 5.4 Резюме Литература |
185 185 185 187 189 191 193 194 195 197 197 199 200 201 202 205 207 207 208 210 211 213 219 220 220 222 225 226 228 229 230 |
|
|
|
ГЛАВА 6. Автоматы с
магазинной памятью 6.1. Определение
автоматов с магазинной памятью 6.1.1.
Неформальное введение 6.1.2.
Формальное определение автомата с магазинной памятью 6.1.3.
Графическое представление МП-автоматов 6.1.4.
Конфигурации МП-автомата 6.1.5.
Упражнения к разделу 6.1 6.2. Языки
МП-автоматов 6.2.1.
Допустимость по заключительному состоянию 6.2.2.
Допустимость по пустому магазину 6.2.3.
От пустого магазина к заключительному состоянию 6.2.4.
От заключительного состояния к пустому магазину 6.2.5.
Упражнения к разделу 6.2 6.3. Эквивалентность
МП-автоматов и КС-грамматик 6.3.1.
От грамматик к МП-автоматам 6.3.2.
От МП-автоматов к грамматикам 6.3.3.
Упражнения к разделу 6.3 6.4. Детерминированные
автоматы с магазинной памятью 6.4.1.
Определение детерминированного МП-автомата Регулярные
языки и детерминированные МП-автоматы 6.4.3.
Детерминированные МП-автоматы и КС-языки 6.4.4.
Детерминированные МП-автоматы и неоднозначные грамматики 6.4.5.
Упражнения к разделу 6.4 Резюме Литература |
233 233 233 235 237 238 241 242 242 244 244 247 249 251 251 255 259 260 260 261 262 263 264 265 266 |
|
|
|
ГЛАВА 7. Свойства
контекстно-свободных языков 7.1. Нормальные
формы контекстно-свободных грамматик 7.1.1.
Удаление бесполезных символов 7.1.2.
Вычисление порождающих и достижимых символов 7.1.3.
Удаление Е-продукций 7.1.4.
Удаление цепных продукций 7.1.5.
Нормальная форма Хомского 7.1.6.
Упражнения к разделу 7.1 7.2. Лемма
о накачке для контекстно-свободных языков 7.2.1.
Размер деревьев разбора 7.2.2.
Утверждение леммы о накачке 7.2.3.
Приложения леммы о накачке к КС-языкам 7.2.4.
Упражнения к разделу 7.2 7.3. Свойства
замкнутости контекстно-свободных языков 7.3.1.
Подстановки 7.3.2.
Приложения теоремы о подстановке 7.3.3.
Обращение 7.3.4.
Пересечение с регулярным языком 7.3.5.
Обратный гомоморфизм 7.3.6.
Упражнения к разделу 7.3 7.4. Свойства
разрешимости КС-языков 7.4.1.
Сложность взаимных преобразований КС-грамматик и
МП- автоматов 7.4.2.
Временная сложность преобразования к нормальной форме Хомского 7.4.3.
Проверка пустоты КС-языков 7.4.4.
Проверка принадлежности КС-языку 7.4.5.
Обзор неразрешимых проблем КС-языков 7.4.6. Упражнения к разделу 7.4 Резюме Литература |
269 269 269 271 273 276 280 284 287 287 288 290 293 295 295 297 298 298 302 304 306 306 308 309 311 314 315 316 317 |
|
|
|
ГЛАВА 8. Введение в
теорию машин Тьюринга 8.1. Задачи,
не решаемые компьютерами 8.1.1.
Программы печати "Hello, world" 8.1.2.
Гипотетическая программа проверки приветствия мира 8.1.3.
Сведение одной проблемы к другой 8.1.4.
Упражнения к разделу 8.1 8.2. Машина
Тьюринга 8.2.1.
Поиски решения всех математических вопросов 8.2.2.
Описание машин Тьюринга 8.2.3.
Конфигурации машин Тьюринга 8.2.4.
Диаграммы переходов для машин Тьюринга 8.2.5.
Язык машины Тьюринга 8.2.6.
Машины Тьюринга и останов 8.2.7.
Упражнения к разделу 8.2 8.3. Техника
программирования машин Тьюринга 8.3.1.
Память в состоянии 8.3.2.
Многодорожечные ленты 8.3.3.
Подпрограммы 8.3.4.
Упражнения к разделу 8.3 8.4. Расширения
базовой машины Тьюринга 8.4.1.
Многоленточные машины Тьюринга 8.4.2.
Эквивалентность одноленточных и многоленточных машин Тьюринга 8.4.3.
Время работы и конструкция "много лент к одной" 8.4.4.
Недетерминированные машины Тьюринга 8.4.5.
Упражнения к разделу 8.4 8.5. Машины
Тьюринга с ограничениями 8.5.1.
Машины Тьюринга с односторонними лентами 8.5.2.
Мультистековые машины 8.5.3.
Счётчиковые машины 8.5.4.
Мощность счётчиковых машин 8.5.5.
Упражнения к разделу 8.5 8.6. Машины
Тьюринга и компьютеры 8.6.1.
Имитация машины Тьюринга на компьютере 8.6.2.
Имитация компьютера на машине Тьюринга 8.6.3.
Сравнение времени работы компьютеров и машин Тьюринга Резюме Литература |
319 319 320 322 325 328 328 329 330 331 334 337 338 339 340 340 342 344 346 346 347 348 349 351 353 355 356 358 361 362 364 365 365 366 371 374 376 |
|
|
|
ГЛАВА 9. Неразрешимость 9.1. Неперечислимый
язык 9.1.1.
Перечисление двоичных цепочек 9.1.2.
Коды машин Тьюринга 9.1.3.
Язык диагонализации 9.1.4.
Доказательство неперечислимости Ld 9.1.5.
Упражнения к разделу 9.1 9.2. Неразрешимая
РП-проблема 9.2.1.
Рекурсивные языки 9.2.2.
Дополнения рекурсивных и РП-языков 9.2.3.
Универсальный язык 9.2.4.
Неразрешимость универсального языка 9.2.5.
Упражнения к разделу 9.2 9.3. Неразрешимые
проблемы, связанные с машинами Тьюринга 9.3.1.
Сведения 9.3.2.
Машины Тьюринга, допускающие пустой язык 9.3.3.
Теорема Раиса и свойства РП-языков 9.3.4.
Проблемы, связанные с описаниями языков в виде машин Тьюринга 9.3.5.
Упражнения к разделу 9.3 9.4. Проблема
соответствий Поста 9.4.1.
Определение проблемы соответствий Поста 9.4.2.
"Модифицированная" ПСП 9.4.3.
Завершение доказательства неразрешимости ПСП 9.4.4.
Упражнения к разделу 9.4 9.5. Другие
неразрешимые проблемы 9.5.1.
Проблемы, связанные с программами 9.5.2.
Неразрешимость проблемы неоднозначности КС-грамматик 9.5.3.
Дополнение языка списка 9.5.4.
Упражнения к разделу 9.5 Резюме Литература |
377 378 378 379 380 381 382 382 383 385 387 389 390 392 392 394 397 399 400 401 402 404 407 412 413 413 413 416 418 420 421 |
|
|
|
ГЛАВА 10. Труднорешаемые
проблемы 10.1. Классы
P и NP 10.1.1.
Проблемы, разрешимые за полиномиальное время 10.1.2.
Пример: алгоритм Крускала 10.1.3.
Недетерминированное полиномиальное время 10.1.4.
Пример из NP: проблема коммивояжера 10.1.5.
Полиномиальные сведения 10.1.6.
NP-полные проблемы 10.1.7.
Упражнения к разделу 10.1 10.2. Первая
NP-полная проблема 10.2.1.
Проблема выполнимости 10.2.2.
Представление экземпляров ВЫП 10.2.3.
NP-полнота проблемы ВЫП 10.2.4.
Упражнения к разделу 10.2 10.3. Ограниченная
проблема выполнимости 10.3.1.
Нормальные формы булевых выражений 10.3.2.
Преобразование формул в КНФ 10.3.3.
NP-полнота проблемы ВКНФ 10.3.4.
NP-полнота проблемы 3-выполнимости 10.3.5.
Упражнения к разделу 10.3 10.4. Еще
несколько NP-полных проблем 10.4.1.
Описание NP-полных проблем 10.4.2.
Проблема независимого множества 10.4.3.
Проблема узельного покрытия 10.4.4.
Проблема ориентированного гамильтонова цикла 10.4.5.
Неориентированные гамильтоновы циклы и ПКОМ 10.4.6.
Вывод относительно NP-полных проблем 10.4.7.
Упражнения к разделу 10.4 Резюме Литература |
423 424 424 424 429 429 431 432 434 436 436 438 439 445 445 446 447 450 455 456 457 458 458 462 464 470 472 473 477 478 |
|
|
|
ГЛАВА 11. Дополнительные
классы проблем 11.1. Дополнения
языков из NP 11.1.1. Класс языков co-NP 11.1.2. NP-полные проблемы и co-NP 11.1.3.
Упражнения к разделу 11.1 11.2. Проблемы, разрешимые в
полиномиальном пространстве 11.2.1.
Машины Тьюринга с полиномиальным пространством 11.2.2.
Связь PS и NPS с определёнными ранее классами 11.2.3.
Детерминированное и недетерминированное полиномиальное пространство 11.3. Проблема, полная для PS 11.3.1.
PS-полнота 11.3.2.
Булевы формулы с кванторами 11.3.3.
Вычисление булевых формул с кванторами 11.3.4.
PS-полнота проблемы КБФ 11.3.5.
Упражнения к разделу 11.3 11.4. Классы языков, основанные на
рандомизации 11.4.1.
Быстрая сортировка – пример рандомизированного алгоритма 11.4.2.
Вариант машины Тьюринга с исползованием рандомизации 11.4.3.
Язык рандомизированной машины Тьюринга 11.4.4.
Класс RP 11.4.5.
Распознавание языков из RP 11.4.6.
Класс ZPP 11.4.7.
Соотношение между RP и ZPP 11.4.8.
Соотношения с классами P и NP 11.5. Сложность проверки простоты 11.5.1.
Важность проверки пустоты 11.5.2.
Введение в модулярную арифметику 11.5.3.
Сложность вычислений в модулярной арифметике 11.5.4.
Рандомизированная полиномиальная проверка простоты 11.5.5.
Недетерминированные проверки простоты 11.5.6.
Упражнения к разделу 11.5 Резюме Литература Предметный указатель |
481 482 482 483 484 485 485 486 487 489 490 491 492 494 498 499 499 500 502 504 506 506 507 509 509 510 514 512 515 516 519 520 521 523 |
|
|
|
|
|
|