Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений 2-Е ИЗДАНИЕ ДЖОН ХОПКРОФТ РАДЖИВ МОТВАНИ ДЖЕФФРИ УЛЬМАН Москва ° Санкт-Петербург ° Киев 2002 ББК 32.973.26-01 8.2.75 Х78 УЛК 681.3.07 Издательский дом "Вильямс" Перевал с английского О.о. Васьтык, АГ. Саит- !истова, канд.физ.-мат.наук А.Б. Ставровского Под редакцией канл.физ.-мат.наук А.Б.

Стаеровского По общим вопросам обращайтесь в Издательский дом "Вильямс" по адресу: )пГо(шм)11)ашврцЫ)зЫпй.сош, Ьцрлгмччм,м!!БашзрцЫ(зЫпй.сею !БВ)Ч 5-8459-026! -4 (рус.) Книга известных американских ученых посвящена теории автоматов и соответствующих формальных языков и грамматик - как регулярных, так и контекстно- свободных.

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

Никакая часть настоящего издания ии в каких целях не может быть воспроизведена в какой бы то ни было форме и какилзи бы то ии было средствами, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, если на это нет пиеьмеиито разрешения издательства Абб(зоп-туев(еу Рпы)льшв Сатрапу, Ые. Ацйопаед !галл!акоп !тош йе Епяйзй )апйзаяе еййоп рпЫВЬеб Ьу Абб!зоп-Фез)еу РцЬйс | 8 Сопзрапу, 1пс, Сорупйй Ю 2001 Ай цвыл гелегчей Ыо раг! оГ йи Ьоой пзау Ье гергойцсед ог (гаплпццед !и апу Гогш ог Ьу апу шеапз, е(ее!гоп!е ог пзееЬап(еа).

(пе!цб!пя рьоюеору!пй, гееогсйпя ог Ьу апу !пГоппапоп могаяе генйеча) зумегп, мИЛош реппимоп !гош йе РпЫВЬег. Выпал 1апбцаве ейцоп рпЬйьйед Ьу 591)йашл РпЫВЫпй Ноеве асеогйпя го йе Аягеепзеп! мИЬ йх! Епгег)згззез 1пгегпагюпа1„Сорупвш гы 2002 0 Издательский долл "В илья лзе", 2002 С Адйлоп-(уез1еу РпЫВЫпя Сошрапу, (пс„200! !5ВМ 5-8459-0261-4 (рус.) 15ВН 0-201-44124-1(англ.) Хонкрофт, Джон, Э., Мотванн, Раджив, Ульман, Джеффри, Д.. Х78 Введение в теорию автоматов, языков и вычислений, 2-е изд..: Пер. с англ.— М.: Издательский дом "Вильямс", 2002.

— 528 с.: ил. — Парал. тит, англ. Оглавление Предисловие ГЛАВА 1. Автоматы: методы и понятия ГЛАВА 2. Конечные автоматы ГЛАВА 3. Регулярные выражения и языки ГЛАВА 4. Свойства регулярных языков ГЛАВА 5. Контекстно-свободные грамматики и языки ГЛАВА 6. Автоматы с магазинной памятью ГЛАВА 7. Свойства контекстно-свободных языков ГЛАВА 8.

Введение в теорию машин Тьюринга ГЛАВА 9. Неразрешимость ГЛАВА 10. Труднорешаемые проблемы ГЛАВА 11. Дополнительные классы проблем Предметный указатель 14 101 143 185 233 269 319 377 423 481 523 Содержание 14 15 15 16 16 16 ГЛАВА 2. Конечные автоматы 53 54 54 55 57 СОДЕРЖАНИЕ Предисловие Как пользоваться книгой Требования к уровню подготовки Упражнения Поддержка в %ог14 %1бе туеЬ Благодарности ГЛАВА 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. Проблемы Резюме Литература 2.1. Неформальное знакомство с конечными автоматами 2.1.1.

Основные правила 2.1.2. Протокол 2.1.3. Возможность игнорирования автоматом некоторых действий 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.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.! . Поиск цепочек в тексте 2.4.2.

Недетерминированные конечные автоматы для поиска в тексте 2.4.3. ДКА, распознающий множество ключевых слов 2.4,4. Упражнения к разделу 2,4 2.5. Конечные автоматы с эпсилон-переходами 2.5.!. Использование е-переходов 2.5.2.Формальная запись е-НКА 2.5.3. Что такое в-замыкание 2.5.4. Расширенные переходы и языки е-НКА 2.5.5. Устранение в-переходов 2.5.6. Упражнения к разделу 2.5 Резюме Литература ГЛАВА 3. Регулярные выражения и языки 3.1. Регулярные выражения 3.1.1. Операторы регулярных выражений 3.! .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 З.З. Применение регулярных выражений 59 61 6! 62 62 64 65 68 69 7! 72 73 74 75 77 81 83 85 85 86 87 89 89 89 91 9! 92 94 97 97 98 1О1 101 102 104 106 108 108 109 !14 !20 124 126 СОДЕРЖАНИЕ 3.3.1.

Регулярные выражения в БХ1Х 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 Резюме Литература ГЛАВА 4.

Свойства регулярных языков 4.!. Доказательство нерегулярности языков 4.1.1. Лемма о накачке для регулярных языков 4.!.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 Резюме Литература ГЛАВА 5. Контекстно-свободные грамматики и языки 5.1. Контекстно-свободные грамматики 5.1.1. Неформальный пример 5.1.2. Определение контекстно-свободных грамматик 5.1.3, Порождения с использованием грамматики 126 128 130 132 132 133 134 134 135 136 136 139 140 141 142 14З 143 144 145 147 148 149 154 156 157 163 166 167 169 170 171 171 г72 175 177 180 182 183 183 185 185 185 187 189 СОДЕРЖАНИЕ ности СОДВРжАНИВ 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. Генератор синтаксических анализаторов УАСС 5.3.3. Языки описания документов 5.3.4. ХМ1. и определения типа документа 5.3.5. Упражнения к разделу 5.3 5.4. Неоднозначность в грамматиках и языках 5.4.1. Неоднозначные грамматики 5.4,2.

Исключение неоднозначности из грамматик 5.4.3. Левые порождения как способ выражения неоднознач 5.4.4. Сушественная неоднозначность 5.4.5. Упражнения к разделу 5.4 Резюме Литература ГЛАВА 6. Автоматы с магазинной памятью 6.1. Определение автоматов с магазинной памятью 6.1.1. Неформальное введение 6.1.2. Формальное определение автомата с магазинной памятью 6,1.3. Графическое представление МП-автоматов 6.1.4. Конфигурации МП-автомата 6.1,5. Упражнения к разделу 6.1 6.2.