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

127 .л, 127 Операция днагонализации, 381 замыкания, 215 Определение типа документа, 207; 214 Оракул, 434 Останов машины Тьюринга, 338 Остаток, 251 Палиндром, 185; 234 Пара цепная, 277 Переключательная игра Шеннона, 499 Переменная е-порождающая, 273 булеза, 436 грамматики, 187 Перемещнвание цепочек, 305 языков 305 Пересечение с регулярным языком, 299 языков, 149 Перестановка цепочки, 305 Переход машины Тьюринга, 330 Питтс Э., 98 Подстановка, 295 значений переменных, 437 удовлетворяющая форллуле, 437 Поиск цепочек в тексте, 85 Покрытие графа реберное, 462 минимальное,462 узельнае, 463 минимальное, 463 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 626 т с Полнота по Карпу, 434 по Куку, 434 Порождение, ! 89 левое, 191 правое, 191 Порядок числа, 514 Пост Э., 402 Посылка,22 Правило пнх1цз ранена, 24 логическое,24 Правило вывода, 187 Префиксное свойство, 262 Принцип голубятни, 82 индукции, 37 Приоритет регулярного оператора, 106 Пробел, 331 Проблема, 48 "са!!з-Гоо", 326 "йе!1о.

чтагЫ', 321 2ВЫП, 457 ЗВЫП, 447; 455 З-выполнимости, 455 К-ВЫП, 446 1хр-полная, 432 Хр-трудная, 17; 433 РЯ-полная, 490 ВКПФ, 446; 450 выполнимости, 437 гамильтонова пути, 476 цикла, 464 доминирующего множества, 475 изоморфизма подграфа, 475 КБФ, 494 клики, 473 коммивояжера, 429; 471 невыполнимости,482 независимого множества, 459 неориентированного гамильтонова цикла, 470 неразрешимая, 323; 325, 383 ориентированного гамильтонова цикла, 464 астапова, 389 пожзрных депо, 475 половинной клики,475 принадлежности цепочки языку, 166 пустоты языка, 166 разбиения, 476 разрешимая, 323; 338; 383 раскраски графа, 473 расписания, 475 реберного покрытия обратных связей, 475 соответствий Поста, 402 модифицированная,404 ТАВТ, 483 точного покрытия, 476 труднорешаемая,17 узельного покрытия,463 формулы с кванторами, 494 эквивалентности, 166 Программа приветствия мира, 320 Программное обеспечение, 18 Продукция, 187 цепная, 2691 276 Пространство полиномиальнае,485 недетерминированное, 485 Протокол, 55 Путь гамильтонов, 476 ориентированный.476 Рабин М,„ 99 Равносильность, 28 Разбиение множества состояний, 178 Различимость состояний, 172; 177 Разложение на простые сомножители, 510 Разность усеченная,335 языков, 153 Райс Х., 398 Регистр„368 Регулярный оператор, 102 Решение проблемы соответствий Поста, 402 Ритчи Д., 320 Сведение полиномиальное, 424 проблем полиномиальнце, 432 проблемы, 325 Сводимость проблем, 392 Свойства замкнутости регулярных языков, 148 КС-языков, 295 Свойство префиксностн, 262 РП-языков, 397 Сети Р., 142 Символ бесполезный.

269 входной, 19; 62 достижимый, 270 ленточный„330 полезный, 269 порожлающий, 270 пустой, 330 стартовый, 187 терминачьный, 187 Синтаксическая категория, !87 Скотт Д, 99 Слагаемое, 224 Слелствие логическое, 23 Слово, 46 зарезервированное, 130 ключевое, 86; 130 памяти, 367 Сложность временная, 424 Сомножитель, 223 Состояние, 62 допускающее, 19; 62; 331 достижимое, 61 дьявольское, 84 заключительное, 62; ЗЗ! начальное, 19; 62; 331 Степень узла 477 Стокмейер Л., 521 Савич У., 489 Таблица переходов, 65 Тавтология, 483 ТАГ-система Поста, 412 Тезис Чсрча-Тьюринга, 330 Тело продукции, 187 Теорема, 34 Кука, 439 Райса,398 Сэвича, 489 Ферма великая, 321 малая, 514 Терм, 224 Терминал, 187 Томпсон К.,! 42 Тьюринг А,„329 626 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ч Ш Цепочка, 46 627 Узел дерева, 40 внутренний, 198 Удьман Дж., 14; 52; 142 Утверждение, 22 обратное, ЗЗ противоположному, 32 Фактор, 223 Ферма П., 321 Формула булсва, 436 выполнимая,437 с кванторами, 491 Функция Аккермана, 390 переходов, 62 ДКА расширенная, 66 машины Тьюринга, 331 НКА, 74 НКА расширенная, 74 рекурсивная, 390 частичная, 340 Характеристический вектор языка, 381 Хаффмен Д., 98 Хомский Н.„280 Хопкрофт Дж., 14 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ выводимая, 194 левовыводимая, 194 обратная.

154 правовыводимая,!94 пустая, 46 Цикл гамильтонов,430 инструиши компьютера, 369 Черч А., 330 Чисдо Кармайкла, 516 простое, 510 псевдосдучайное, 499 составное, 510 Шеннон К„99, 499 Шифрование, 511 с открьпыми ключами, 5!! Эквивалентность, 28 булевых формул, 447 ДКА и НКА, 77 МП-автоматов, 242 МП-автоматов и КС- грамматик, 251 порождения и деревьев разбора, 200 регудярных выражений, 132 регулярных выражений и конечных автоматов, 109 состояний, 172; !77 Элемент ведущий, 500 единичный,!34 нейтральный относительно конкатенации.

47 нулевой, !34 Язык, 47 !4р-полный, 43 2 грамматики, 189; 193 диагонализации, 380 ДКА, 68 допускаемый по заключительному состоянию, 242 по пустому магазину, 244 контекстно-свободный, 193 машины Тьюринга, 337 неперечисдимый, 383 нерегулярный, 145 НКА, 75 однозначный, 226 описания докуменюв, 211 палиндромов, 186 пустой.

48 регулярного выражения, ! 04 регулярный, 69 рекурсивно перечислимый, 337: 378 рекурсивный, 338; 383 универсальный, 387 Ямвда Х., 142 Научно-популярное издание Джон Э. Хоикрофт, Раджив Мотвани, Джеффри Д. Ульман Введение в теорию автоматов, языков и вычислений 2-е изд. Издательский дом "Вильямс*'. 101509, Москва, ул. Лесная, д. 43, стр. 1. Изд. лиц. ЛР гй 090230 от 23.06.99 Госкомитета РФ но печати.

Подписано в печать 27.03.2002. Формат 70х100/16 Гарнитура Тепел. Печать офсетная. Уел. печ. л, 42,57. Уч.-изд. л. 29,99. Тираж 3500 экз. Заказ 1чз 707. Отпечатано с диапозитивов в ФГУП "Печатный двор" Министерства РФ по делам печати, телерадиовешания и средств массовых коммуникапий. 197110, Санкт-Петербург, Чкаловский пр., 15. Литературный редактор Верстка Художественный редактор Обложка Корректоры О. Ю. Белозовская МА. Удавов Т А. Тараброва С.А. Чернокозинский Л.А. Гордиенко, О.В.

Л1ишутина .