2-Е ИЗДАНИЕ. ДЖОН ХОПКРОФТ РАДЖИВ МОТВАНИ ДЖЕФФРИ УЛЬМАН.

Перевод с английского О. И. Васылык, М. Саит-Аметова, канд.физ.-мат.наук А.Б. Ставровского
Под редакцией канд.физ.-мат.наук А. Б. Ставровского

Книга известных американских ученых посвящена теории автоматов и соответст¬вующих формальных языков и грамматик — как регулярных, так и контекстно- свободных. Во второй части рассматриваются различные машины Тьюринга, при помо¬щи которых формализуются понятия разрешимых и неразрешимых проблем, а также определяются функции временной и емкостной оценки сложности алгоритмов. Изложе¬ние ведется строго, но доступно, и сопровождается многочисленными примерами, а также задачами для самостоятельного решения.

Книга будет полезна читателям различных категорий — студентам, аспирантам, науч¬ным сотрудникам, преподавателям высших учебных заведений, а также всем, кто инте¬ресуется математическими основами современной вычислительной техники.
ББК 32.973.26-018.2.75
Все названия программных продуктов являются зарегистрированными торговыми марками соот¬ветствующих фирм.
Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, если на это нет письменного разрешения издатель¬ства Addison-Wesley Publishing Company, Inc.
Authorized translation from the English language edition published by Addison-Wesley Publishing Company, Inc, Copyright © 2001
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mcchanical, including photocopying, recording or by any information storage retrieval system, without permission from the Publisher.
Russian language edition published by Williams Publishing House according to the Agreement with R&l Enterprises International, Copyright © 2002

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