dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (Введение в теорию автоматов)

Введение в теориюавтоматов, языкови вычислений2Е ИЗДАНИЕtitle.indd 107.11.2007 16:57:18Introduction to AutomataTheory, Languages, andComputationSECOND EDITIONJOHN E. HOPCROFTCornell UniversityRAJEEV MOTWANIStanford UniversityJEFFREY D. ULLMANStanford UniversityADDISONWESLEY PUBLISHING COMPANYBoston · San Francisco · New YorkLondon · Toronto · Sydney · Tokyo · Singapore · MadridMexico City · Munich · Paris · Cape Town · Hong Kong · Montrealtitle.indd 207.11.2007 16:57:19Введение в теориюавтоматов, языкови вычислений2Е ИЗДАНИЕДЖОН ХОПКРОФТРАДЖИВ МОТВАНИДЖЕФФРИ УЛЬМАНМосква · СанктПетербург · Киев2008title.indd 307.11.2007 16:57:19ББК 32.973.26-018.2.75Х78УДК 681.3.07Издательский дом “Вильямс”Перевод с английского О.И. Васылык, М. Саит-Аметова,канд.физ.-мат.наук А.Б.

СтавровскогоПод редакцией канд.физ.-мат.наук А.Б. СтавровскогоПо общим вопросам обращайтесь в Издательский дом “Вильямс”по адресу: info@williamspublishing.com, http://www.williamspublishing.comХопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д..Х78Введение в теорию автоматов, языков и вычислений, 2-е изд.. : Пер.

с англ. —М. : Издательский дом “Вильямс”, 2008. — 528 с. : ил. — Парал. тит. англ.ISBN 978-5-8459-1347-0 (рус.)Книга известных американских ученых посвящена теории автоматов и соответствующих формальных языков и грамматик - как регулярных, так и контекстносвободных. Во второй части рассматриваются различные машины Тьюринга, при помощи которых формализуются понятия разрешимых и неразрешимых проблем, а такжеопределяются функции временной и емкостной оценки сложности алгоритмов. Изложение ведется строго, но доступно, и сопровождается многочисленными примерами, атакже задачами для самостоятельного решения.Книга будет полезна читателям различных категорий - студентам, аспирантам, научным сотрудникам, преподавателям высших учебных заведений, а также всем, кто интересуется математическими основами современной вычислительной техники.ББК 32.973.26-018.2.75Все названия программных продуктов являются зарегистрированными торговыми марками соответствующих фирм.Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы тони было форме и какими бы то ни было средствами, будь то электронные или механические, включаяфотокопирование и запись на магнитный носитель, если на это нет письменного разрешения издательства Addison-Wesley Publishing Company, Inc.Authorized translation from the English language edition published by Addison-Wesley PublishingCompany, Inc, Copyright © 2001All rights reserved.

No part of this book may be reproduced or transmitted in any form or by any means,electronic or mechanical, 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&IEnterprises International, Copyright © 2008ISBN 978-5-8459-1347-0 (русISBN 0-201-44124-1 (англ.)Стр. 4© Издательский дом “Вильямс”, 2008© Addison-Wesley Publishing Company, Inc, 2001ÎãëàâëåíèåСтр.

5Предисловие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Как пользоваться книгойТребования к уровню подготовкиУпражненияПоддержка в World Wide WebБлагодарности1515161616ГЛАВА 1. Автоматы: методы и понятия171.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. Конечные автоматы532.1. Неформальное знакомство с конечными автоматами2.1.1. Основные правила2.1.2. Протокол2.1.3. Возможность игнорирования автоматом некоторых действий6Стр. 6181820212122252730303032343436363940434546464748505254545557ÑÎÄÅÐÆÀÍÈÅ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.22.3.

Недетерминированные конечные автоматы2.3.1. Неформальное описание недетерминированного конечногоавтомата2.3.2. Определение недетерминированного конечного автомата2.3.3. Расширенная функция переходов2.3.4. Язык НКА2.3.5. Эквивалентность детерминированных и недетерминированныхконечных автоматов2.3.6. Плохой случай для конструкции подмножеств2.3.7. Упражнения к разделу 2.32.4. Приложение: поиск в тексте2.4.1. Поиск цепочек в тексте2.4.2. Недетерминированные конечные автоматы для поиска в тексте2.4.3. ДКА, распознающий множество ключевых слов2.4.4.

Упражнения к разделу 2.42.5. Конечные автоматы с эпсилон-переходами2.5.1. Использование ε-переходов2.5.2. Формальная запись ε-НКА2.5.3. Что такое ε-замыкание2.5.4. Расширенные переходы и языки ε-НКА2.5.5. Устранение ε-переходов2.5.6. Упражнения к разделу 2.5РезюмеЛитератураГЛАВА 3. Регулярные выражения и языки3.1. Регулярные выражения3.1.1. Операторы регулярных выражений3.1.2. Построение регулярных выражений3.1.3. Приоритеты регулярных операторов3.1.4. Упражнения к разделу 3.13.2. Конечные автоматы и регулярные выражения3.2.1. От ДКА к регулярным выражениям3.2.2. Преобразование ДКА в регулярное выражение методомисключения состояний3.2.3. Преобразование регулярного выражения в автомат3.2.4.

Упражнения к разделу 3.23.3. Применение регулярных выраженийÑÎÄÅÐÆÀÍÈÅСтр. 75961616262646568697172737475778183858586878989899191929497979810110110210410610810810911412012412673.3.1. Регулярные выражения в UNIX3.3.2. Лексический анализ3.3.3. Поиск образцов в тексте3.3.4. Упражнения к разделу 3.33.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. Свойства регулярных языков5.1. Контекстно-свободные грамматики5.1.1.

Неформальный пример5.1.2. Определение контекстно-свободных грамматик5.1.3. Порождения с использованием грамматики8Стр. 81391401411421434.1. Доказательство нерегулярности языков4.1.1. Лемма о накачке для регулярных языков4.1.2. Применение леммы о накачке4.1.3. Упражнения к разделу 4.14.2. Свойства замкнутости регулярных языков4.2.1. Замкнутость регулярных языков относительно булевых операций4.2.2. Обращение4.2.3. Гомоморфизмы4.2.4. Обратный гомоморфизм4.2.5. Упражнения к разделу 4.24.3.

Свойства разрешимости регулярных языков4.3.1. Преобразования различных представлений языков4.3.2. Проверка пустоты регулярных языков4.3.3. Проверка принадлежности регулярному языку4.3.4. Упражнения к разделу 4.34.4. Эквивалентность и минимизация автоматов4.4.1. Проверка эквивалентности состояний4.4.2. Проверка эквивалентности регулярных языков4.4.3. Минимизация ДКА4.4.4.

Почему минимизированный ДКА невозможно улучшить4.4.5. Упражнения к разделу 4.4РезюмеЛитератураГЛАВА 5. Контекстно-свободные грамматики и языки126128130132132133134134135136136143144145147148149154156157163166167169170171171172175177180182183183185185185187189ÑÎÄÅÐÆÀÍÈÅ5.1.4. Левые и правые порождения5.1.5. Язык, задаваемый грамматикой5.1.6.

Выводимые цепочки5.1.7. Упражнения к разделу 5.15.2. Деревья разбора5.2.1. Построение деревьев разбора5.2.2. Крона дерева разбора5.2.3. Вывод, порождение и деревья разбора5.2.4. От выводов к деревьям разбора5.2.5. От деревьев к порождениям5.2.6.

От порождений к рекурсивным выводам5.2.7. Упражнения к разделу 5.25.3. Приложения контекстно-свободных грамматик5.3.1. Синтаксические анализаторы5.3.2. Генератор синтаксических анализаторов YACC5.3.3. Языки описания документов5.3.4. XML и определения типа документа5.3.5. Упражнения к разделу 5.35.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.16.2. Языки МП-автоматов6.2.1. Допустимость по заключительному состоянию6.2.2. Допустимость по пустому магазину6.2.3. От пустого магазина к заключительному состоянию6.2.4. От заключительного состояния к пустому магазину6.2.5. Упражнения к разделу 6.26.3. Эквивалентность МП-автоматов и КС-грамматик6.3.1. От грамматик к МП-автоматам6.3.2.