Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 101
Текст из файла (страница 101)
Итак, если М допускает вход н, и 1и ~ = и, то существует последовательность переходов Мсо следующими свойствами. 1. ас — исходное МО Мсо входом ж. 2. ае 1- ае, 1-" 1- аьгде1с<р(и). 3. ас — МО с допускающим состоянием. 10.2. ПЕРВАЯ 1чР-ПОЛНАЯ ПРОБЛЕМА 439 4. Каждое а, не содержит пробелов (за исключением тех аь которые заканчиваются состоянием и пробелом) и располагается вправо от исходной позиции головки— крайнего слева входного символа. Стратегия построения формулы вкратце такова.
1. Каждое ьх может быть записано как последовательность символов ХвХн...Хь„~ы длиной р(п) ь 1. Один из них — состояние, а остальные р(п) — ленточные символы. Как обычно, предположим, что множества состояний и ленточных символов не пересекаются, так что можно отличить, какое из Х, является состоянием, и указать, где находится головка.
Отметим, что нет надобности представлять символы, расположенные справа от первых р(п) символов на ленте, поскольку, если М гарантированно останавливается, сделав не более р(п) переходов, то на переходы М эти символы справа не влияют. 2. Для описания последовательности МО в терминах булевых переменных введем переменные у„л, которые представляют утверждения вида Хз = А. Здесь ! и у — целые из интервала от 0 до р(п), а А — либо ленточный символ, либо состояние. 3. Условие того, что последовательность МО представляет допускание, записывается в виде булевой формулы, выполнимой тогда и только тогда, когда Мдопускает н в результате последовательности не более чем р(п) переходов. Удовлетворяющая подстановка "характеризует" МО, т.е. уьв истинна тогда и только тогда, когда Х, = А.
Для гарантии того, что полиномиальное сведение ЦМ) к ВЫП корректно, эта формула записывается так, чтобы отражать следуюшие свойства вычисления. !. Правильный старт — исходное МО есть а,ш с последуюшими пробелами. й. Правильные переходы (т,е, согласующиеся с правилами МТ) — каждое последующее МО получается из предыдушего путем выполнения одного из возможных законных переходов М. ш. Правильный финиш — сушествует МО с допускающим состоянием. Прежде, чем точно описать построение нашей булевой формулы, рассмотрим несколько деталей. ° Во-первых, по построению МО заканчивается там, где начинается бесконечный "хвост" из пробелов.
Однако, имитируя вычисление за полиномиальное время, удобнее считать, что все МО имею~ одну и ту же длину р(п) ь !. Поэтому в МО может присутствовать хвост из пробелов. ° Во-вторых, удобно считать, что все вычисления происходят в точности за р(п) переходов (и, следовательно, имеют р(п) -ь 1 МО), даже если допускание происходит раньше. Следовательно, всякому МО с допускающим состоянием позволено быть собственным преемником, т.е., когда а содержит допускаюшее состояние, разрешен "переход" а!- а. Таким образом, можно предполагать, что если ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 440 существует допускающее вычисление, то а ла имеет допускающее состояние, и это все, что нужно проверить в условии (ш). На рис.!0.4 представлен общий вид полииомиального вычисления М.
Строки соответствуют последовательности МО, а столбцы — это клетки на ленте, которые могут использоваться при вычислении. Заметим, что число ячеек на рис. 10.4 равно (р(п) + 1)~. Кроме того, число различных значений переменных, представляющих ячейки, конечно и зависит только от М; оно равно сумме числа состояний и числа ленточных символов М. Рис. П14 Построение массива данных о последовательности МО Приведем теперь алгоритм построения булевой формулы Ехр„.
по М и и. Общий вид Ем„,— Ел Фл Р, где формулы Е, АР и Г говорят о том, что М совершает правильный старт, переходы и финиш. Правильный старт Символ Х„должен быть начальным состоянием «1о машины М, символы с Хт по Х,„— образовывать цепочку и (и — ее длина), а оставшиеся Хй — быть пробелами В, т.е. если в = а,ае... а„, то УоооолУоии лУооог л "' лУоитлУо, -ивлУо, .онл " лУораан. Безусловно, по данным М и и можно записать 5 на второй ленте многоленточной МТ за время 01р(п)). Правильный финиш Поскольку предполагается, что допускающее МО повторяется до бесконечности, то допускание М эквивалентно присутствию допускающего состояния в а р„,.
Напомним, что по предположению М является такой НМТ, которая, если допускает, то делае~ это в пределах 10.2. ПЕРВАЯ тйР-ПОЛНАЯ ПРОБЛЕМА 441 р(п) шагов. Таким образом, В есть логическое ИЛИ формул г! для 1 = О, 1, ..., р(п), где г! утверждает, что Х,!„!, — допускаюшее состояние. т.е. г! есть ур!и>!.и м Угя!зп!" "' мур!ьл!, ! где аь аз, ..., а! — все допускаюшие состояния М.
Тогда л Р!! л! ! ! Рр(е Отметим, что в каждом из Г, используется постоянное число символов, которое зависит от М, а не от длины и входа и. Поэтому В имеет длину ОЯп)). Более важно то, что время, необходимое для записи В по данным коду М и цепочке и, полиномиально зависит от и. В действительности, формулу В можно записать на многоленточной МТ за время 0(р(п)). Правильные переходы Намного сложнее убедиться, что М правильно выполняет переходы.
Формула Д' будет логическим И формул Дп где ! = О, 1, ..., р(п) — 1, и каждое Д!, строится так, чтобы а, ! было одним нз МО, в которые можно перейти из а, по правилам М. Чтобы понять, как следует записать Дг„рассмотрим символ Х ! на рис. 10.4. Символ Х !, всегда можно определить, зная: а) три символа над ним, т,е. Х,, Х, иХ„.!., б) выбор перехода НМТ М, если один из этих символов есть состояние в а,.
Запишем Д!, как логическое И формул А, м В„, где у = О, 1, ..., р(п). ° Формула А„говорит о том, что; а) состояние МО а, находится в позиции /, т.е. Х, — состояние; б) если Մ— состояние и Хо . — обозреваемый символ, то сушествует выбор такого перехода М, который преобразует последовательность символов Х,! !ХД;!, в Х.!, !Х,.!,Х,.! ь Заметим, что если Մ— допускаюшее состояние, то возможен только "выбор", при котором переход вообше не совершается, поэтому все последуюшие МО совпадают с первым, привед- шим к допусканию. ° Формула В„говорит о том, что: а) состояние МО а, достаточно далеко от Х,, так что оно не может влиять на Х !, (ни один из символов Х, !, Хл Х„.! не является состоянием); б) Х...=Х„.
Формулу В„записать легче, чем А„. Пусть дь дз, ..., д — состояния, а У!, Уз, ..., У,— ленточные символы. Тогда Вх = (У,!.!л! ' ' У,! !я! м " '4 и,! ! ьэ) л (Уц ! '4У~!з! ! ''' '4Е!з) л (У. - !зл м Уо ! яг !У!! пга ) л (У, 7! лУ, ! з!) I (гф!з! лУя !(з!)4 м (У,!ил У, !.!у,). ГЛАВА 10. 'ГРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 442 Первая, вторая и третья строчки в В„соответственно выражают, что Х„ь Х, и Х, ленточные символы. Последняя строчка выражает равенство Хь ы = Х,; в ней перечисляются все возможные ленточные символы У, и говорится, что обе переменные — это либо Ль либо 22 и т.д. Сушествует два важных частных случая: / = 0 и у = р(п).
В первом нет переменных у„наь а во втором — переменных у,, ~ ж Однако нам известно, что головка никогда не сдвигается влево от своего исходного положения и что ей не хватит времени, чтобы сдвинуться более чем на р(п) клеток вправо от исходной. Поэтому из Вм и В,р~п можно выбросить некоторые члены. Выполните это упрошенне самостоятельно. Рассмотрим теперь формулы А„. Эти формулы отражают все возможные связи между символами Хо ь Х„, Х, ь Х.ы ь Х,.~ и Х.ы.~ в прямоугольниках размером 2хЗ из массива (см. рис. 10.4), Подстановка символов в каждую из этих шести переменных является правильной, если: а) Х, есть состояние, а Хч 4 и Хч .
— ленточные символы; б) состоянием является только один изХь~ .н, Ха, иХ„~ в) существует переход М, объясняющий, как Х„.~Х,Х„~ превращается в Х...,Х,,Х...,,. Таким образом, для этих шести переменных существует лишь конечное число правильных подстановок символов. Пусть А» будет логическим ИЛИ членов, по одному для каждого множества из шести переменных, образующего правильную подстановку. Предположим, что переход М обусловлен тем, что 4~у, А) содержит (р, С, Е).
Пусть 1)— некоторый ленточный символ М. Тогда Хм ~ХвХм, ~ = ВОА и Х ...Х,,Л;, ы.~ =- р11С— одна из правильных подстановок. Заметим, как эта подстановка отражает изменение МО, вызванное данным переходом М. Член, отражающий эту возможность, имеет вид га за лум ~ луо,ьн луанда гя луоь~о лу, Ы,ьг. Если же Щ А) содержит (р, С, В), т.е. переход такой же, но головка сдвигается вправо, то соответствующая правильная подстановка — это Х ьЛ;~ча = ВдА и Х.ы нЛ,.с~Хая ~ = ыСр Соответствующий член имеет вид уооо лупя луо.ьн лу,.~ нолуз.нхс лу, гпср. Формула А„есть логическое ИЛИ всех правильных членов.
В особых случаях, когда) = О н ) = р(п), нужно внести некоторые изменения, чтобы учесть отсутствие переменныхуак при/< О нли/>р(п), как для Вгг Наконец, А', = (Ам ч В и) л (Ан з В ~) л ." л (А, ~~'~ В раа) "УА0лдгл'''лЖрл 10.2. ПЕРВАЯ 14Р-ПОЛНАЯ ПРОБЛЕМА 443 Несмотря на то что формулы Ал и Ве могут быть очень громоздкими (если М имеет много состояний н?или ленточных символов), нх размер представляет собой константу и не зависит от длины входа и.
Таким образом, длина Дс, есть 0(р(п)), а двина Д'— О(р (и)). Более важно то, что формулу Дс можно записать на ленту многоленточной МТ за время, пропорциональное ее длине, и это время полиномиально зависит от и — длины цепочки и. Завершение доказательства теоремы Кука Конструкция формулы Ем, =ЯлД?лР была описана как функция, зависящая и от М, и от зу, но в действительности только часть Я вЂ” "правильный старт" — зависит от и, причем зависимость эта очень простая (зс находится на ленте начального МО).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
