Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 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.2. Регулярные языки и детерминированные МП-автоматы 191 193 194 195 197 197 !99 2ОО 201 202 го5 207 го7 го8 г1о г11 213 219 220 гго 222 225 226 гг8 229 гзо 233 233 233 235 237 238 241 242 242 244 244 247 249 251 251 255 259 260 260 261 6.4.3.

Детерминированные МП-автоматы и КС-языки 6.4.4. Детерминированные МП-автоматы и неоднозначные грамматики 6.4.5. Упражнения к разделу 6.4 Резюме Литература ГЛАВА 7. Свойства контекстно-свободных языков 7.1. Нормальные формы контекстно-свободных грамматик 7.1.1. Удаление бесполезных символов 7.1.2. Вычисление порождающих и достижимых символов 7.! .3. Удаление е-продукций 7.1.4. Удаление цепных продукций 7.1.5.

Нормальная форма Хомского 7.1.6. Упражнения к разделу 7.! 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.!. Сложность взаимных преобразований КС-грамматик и МП- автоматов 7.4.2. Временная сложность преобразования к нормальной форме Хомского 7.4.3. Проверка пустоты КС-языков 7.4.4. Проверка принадлежности КС-языку 7.4.5. Обзор неразрешимых проблем КС-языков 7.4.6. Упражнения к разделу 7.4 Резюме Литература ГЛАВА 8. Введение в теорию машин Тьюринга 8.! . Задачи, не решаемые компьютерами 8.1.1. Программы печати "Нейо, ног!д" 8.1.2.

Гипотетическая программа проверки приветствия мира 8.1.3. Сведение одной проблемы к другой 8.1.4. Упражнения к разделу 8.1 8.2. Машина Тьюринга 8.2.1. Поиски решения всех математических вопросов 8.2.2. Описание машин Тьюринга 262 263 264 265 266 269 269 269 271 273 276 280 284 287 287 288 290 293 295 295 297 298 298 302 304 306 306 308 309 3!1 3!4 315 316 317 319 319 320 322 325 328 328 329 330 10 СОДЕРЖАНИЕ 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. Сравнение времени работы компьютеров и машин Т Резюме Литература х машин ьюриига ГЛАВА 9. Неразрешимость 9.1. Неперечислимый язык 9.1.!. Перечисление двоичных цепочек 9.1.2.

Коды машин Тьюринга 9.1.3, Язык диагоиализации 9.1.4. Доказательство неперечислимости 1.,г 9.1.5. Упражнения к разделу 9.1 9.2. Неразрешимая РП-проблема 92.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.

Теорема Райса и свойства РП-языков 331 334 337 ЗЗ8 339 340 340 342 344 346 346 347 348 349 351 353 355 356 358 361 362 364 365 365 366 371 374 376 377 378 378 379 380 381 382 382 383 385 387 389 390 392 392 394 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. Литература ГЛАВА 1О. Трудпорешаемые проблемы 10.1. Классы Р и МР 10.1.1. Проблемы, разрешимые за полиномиальное время ! О.! .2. Пример: алгоритм Крускала 10.1.3. Недетерминированное полиномиальное время 10.1.4. Пример из ЛР, проблема коммивояжера 10.1.5. Полиномиальные сведения 10.1.6. ХР-полные проблемы 10.1.7. Упражнения к разделу 10.1 ! 0.2. Первая НР-полная проблема 10.2.!. Проблема выполнимости 10.2.2.

Представление экземпляров ВЫП 10.2.3. ХР-полнота проблемы ВЫП 10.2.4. Упражнения к разделу 10.2 10.3. Ограниченная проблема выполнимости 10.3.1. Нормальные формы булевых выражений 10.3.2. Преобразование формул в КНФ 10.3,3. !АР-полнота проблемы ВКНФ 10.3.4. 1ЧР-полнота проблемы 3-выполнимости 10.3.5. Упражнения к разделу 10.3 10.4. Еше несколько ХР-полных проблем ! 0.4.1.

Описание ХР-полных проблем 10.4.2. Проблема независимого множества ! 0.4.3. Проблема узельного покрытия 10.4.4. Проблема ориентированного гамильтонова цикла 10.4.5. Неориентированные гамильтоновы циклы и ПКОМ ! 0.4.6. Вывод относительно !4Р-полных проблем 10.4.7, Упражнения к разделу 10.4 10.5. Резюме 10.6. Л итература 39с 401 401 402 404 407 412 413 413 413 416 418 420 421 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 12 СОДЕРЖАНИЕ ГЛАВА 11.

Дополнительные классы проблем 11.!. Дополнения языков из ЛР 11.1.1. Класс языков со-МР 11.!.2. 1ЧР-полные проблемы и со-ЛР 11.1.3. Упражнения к разделу 11.1 11,2. Проблемы, разрешимые в полиномиальном пространстве 11.2,1. Машины Тьюринга с полиномиальным пространством 11.2,2. Связь Ро и ЛРо с определенными ранее классами 11.2.3. Детерминированное и недетерминированное полиномиальное пространство 11.3. Проблема, полная лля Ро 11.3.! .

РБ-полнота !!.3.2. Булевы формулы с кванторами 11.3.3. Вычисление булевых формул с кванторами 11.3.4. РБ-полнота проблемы КБФ 11.3.5. Упражнения к разделу 11.3 11.4. Классы языков, основанные на рандомизации 11.4.1. Быстрая сортировка — пример рандомизированного алгоритма 11.4.2. Вариант машины Тьюринга с использованием рандомизации 11,4.3. Язык рандомизированной машины Тьюринга 1 !.4.4.

Класс 7'Р 11.4.5. Распознавание языков из ь;Р 11.4.6. Класс ЯРР 11.4.7. Соотношение между РР и ЯРР 11.4.8. Соотношения с классами 'Р и ЛР 11.5. Сложность проверки простоты 11.5.1. Важность проверки пустоты 11.5.2. Введение в модулярную арифметику 11.5.3. Сложность вычислений в модулярной арифметике 1!.5.4. Рандомизированная полиномиальная проверка простоты ! 1.5.5. Недетерминированные проверки простоты 1! .5.6.

Упражнения к разделу 11.5 Резюме Литература Предметный указатель 4!5!! 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 512 5!4 515 516 519 520 521 523 СОДЕРЖАНИЕ Предисловие В предисловии к своей книге 1979 года, предшествовавшей данному изданию, Дж. Хопкрофт и Дж. Ульман с удивлением отмечали, что за время, прошедшее после выхода их первой книги в !9б9 году, произошел взрыв в развитии теории автоматов. Действительно, книга, вышедшая в 1979 году, содержала множество тем, не затронутых в предыдушей работе, и по объему была почти вдвое больше.

Сравнив эту книгу с книгой 1979 года, вы увидите, что она, как автомобили 1970-х "больше снаружи, ио меньше изнутри". И хотя это может показаться шагом назад, мы считаем такие изменения целесообразными в силу ряда причин. Во-первых, в 1979 году теория автоматов и языков еше активно развивалась, и одной из целей той книги было пробудить интерес математически одаренных студентов к исследованиям в этой области. На сегодня в теории автоматов имеется лишь узкое направление для исследований (чего не скажешь о ее приложениях).

Поэтому, на наш взгляд, не имеет смысла сохранять здесь лаконичный, сугубо математический стиль книги 1979 года. Во-вторых, за последние двадцать лет изменилась роль теории автоматов и языков. В 1979 году это был сложный предмет, требующий от читателя высокого уровня подготовки. Читатель нашей книги, в особенности последних ее глав, представлялся нам хорошо подготовленным студентом-старшекурсником. Сегодня же этот предмет входит в стандартную вузовскую программу дпя младших курсов. Поэтому содержание книги должно быть по возможности доступным, а следовательно, содержать больше подробных доказательств и обоснований по сравнению с предыдущей книгой, В-третьих, за два последних десятилетия информатика (Сотршег Зс1епсе) невообразимо разрослась.

И если в 1979 году вузовскую программу приходилось искусственно заполнять предметами, которые, как нам казалось, могли послужить новой волне развития технологий, то сегодня таких дисциплин уже слишком много. В-четвертых, за эти годы информатика стала практическим предметом, и многие изучающие ее студенты настроены прагматически. Мы по-прежнему убеждены, что теория автоматов является мощным инструментом для исследований во множестве новых областей. А упражнения теоретического, развиваюшего плана, которые содержит обычный курс теории автоматов, сохраняю~ свое значение вне зависимости от того, предпочитает ли студент изучать лишь практические, "денежные" технологии.