Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 82
Текст из файла (страница 82)
4. 5 переходит в начальное (имитируемое) состояние М. Первый магазин 5 пуст, свидетельствуя о том, что у М слева от головки нет ничего, кроме пробелов. Второй магазин 5 содержит ч, отражая тот факт, что справа от головки М находится ч . 5. 5 имитирует переход Мследующим образом: а) Я знает состояние М, скажем, и, поскольку Я имитирует состояние М в своем собственном конечном управлении; б) о знает символ Х, обозреваемый головкой М; это символ на вершине второго магазина о. Как исключение, если второй магазин содержит только маркер дна, то М только что переместилась на пробел; Я интерпретирует символ, обозреваемый М, как пробел; в) итак, Я знает следующий переход М, г) следующее состояние М записывается в компоненте конечного управления Я вместо предыдущего состояния; 360 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА д) если М меняет Х на У и сдвигается вправо, то 5 помещает 1' в свой первый магазин, имитируя то, что У теперь слева от головки М.
Х выталкивается из второго магазина 5. Однако есть два исключения. Если второй магазин содержит только маркер дна (следовательно, Х— пробел), то второй магазин не изменяется; М сдвинулась еше на один пробел вправо, й. Если У вЂ” пробел, и первый магазин пуст; то этот магазин остается пустым. Причина в том, что слева от головки М находятся только пробелы; е) если М меняет Х на 1' и сдвигается влево, то 5 выталкивает символ с вершины первого магазина, скажем, 2, затем меняет Х на тУ во втором магазине. Это изменение отражает, что символ 7, ранее расположенный слева от головки М, теперь обозревается ею. Как исключение, если х является маркером дна, то 5 должна поместить В1'во второй магазин, не выталкивая ничего из первого.
б. 5 допускает, если новое состояние М является допускающим. В противном сл>*чае о имитирует еше один переход М таким же способом. 8.5.3. Счетчиковые машины Счел<чиловую.«пи<илу можно представить одним из двух способов, 1. Счетчиковая машина имеет ~акую же структуру, как и м>льтистековая (см. рис. 3.20), но вместо магазинов у нее счетчики. Счетчики содержат произвольные неотрицательные целые числа, но отличить можно только ненулевое от нулевого. Таким образом, переход счетчиковой машины зависит от ее состояния, входного символа и того, какие из счетчиков являются нулевыми.
За один переход машина может изменить состояние и добавить или отнять 1 от любого из счетчиков. Однако счетчик не может быть отрицательным, поэтому отнимать 1 от счетчика со значением О нельзя. 2. Счетчиковая машина также может рассматриваться, как мультистековая машина со следующими ограничениями; а) есть только два магазинных символа, х«(маркер д«а) и Х; б) вначале х, находится в каждом магазине; в) 2«можно заменить только цепочкой видаЛ'Д для некоторого < > О; г) Х можно заменить только цепочкой видаЛ' для некоторого < > О. Таким образом, У«встречается только на дне каждого магазина, а все остальные символы (если есть) — это символы Х. Для счетчиковых машин будем использовать определение 1, хотя оба они, очевидно, задают машины одинаковой мощности. Причина в том, что магазин Л"Д может быть идентифицирован значением О В определении 2 значение О можно отличить от осталь- 8.5.
МАШИНЫ ТЬЮРИНГА С ОГРАНИЧЕНИЯМИ ных, поскольку значению 0 соответствует 2, на вершине магазина, в противном случае там помещается Х. Однако отличить два положительных числа невозможно, поскольку обоим соответствует Хна вершине магазина. 8.5.4. Мощность счетчиковых машин О языках счетчиковых машин стоит сделать несколько очевидных замечаний. ° Каждый язык, допускаемый счетчиковой машиной, рекурсивно перечислим. При- чина в том, что счетчиковые машины являются частным случаем магазинных, а магазинные — частным случаем многоленточных машин Тьюринга, которые по теореме 8.9 допускают только рекурсивно перечислимые языки.
° Каждый язык, допускаемый односчетчиковой машиной, является КС-языком. Заметим, что счетчик, с точки зрения определения 2, является магазином, поэтому односчетчиковая машина представляет собой частный случай одномагазинной, т.е. МП-автомата. Языки односчетчиковых машин допускаются детерминированными МП-автоматами, хотя доказать это на удивдение сложно.
Трудность вызывает тот факт, что мультистековые и счетчиковые машины имеют маркер 3 в конце входа. Недетерминированный МП-автомат может "догадаться", что он видит последний входной символ, и следующим будет маркер. Таким образом, ясно, что недетерминированный МП-автомат без концевого маркера может имитировать ДМП-автомат с маркером. Однако доказать, что ДМП-автомат без концевого маркера может имитировать ДМП-автомат с маркером, весьма трудно, и мы этого не делаем. Удивительно, но для имитации машины Тьюринга и, следовательно, лля допускания любо~о рекурсивно перечислимого языка, достаточно двух счетчиков.
Для обоснования этого утверждения вначале доказывается, что достаточно трех счетчиков, а затем три счетчика имитируются с помощью двух. Теорема 8.14. Каждый рекурсивно перечислимый язык допускается трехсчетчиковой машиной. Доказательство. Начнем с теоремы 3.!3, утверждавшей, что каждый рекурсивно перечислимый язык допускается двухмагазинной машиной. С ее использованием нам достаточно показать, как магазин имитируется с помощью счетчиков.
Предположим, магазинная машина использует г — 1 ленточных символов. Можно обозначить символы цифрами от ! ло г — ! и рассматривать магазин ХХз...Х, как целое число по основанию г, т.е, этот магазин (его вершина, как обычно, слева) представлен целым числом Х„г +Х„~г" + ...
+Хг+Хь Используем два счетчика для хранения целых чисел, представляющих каждый из двух магазинов. Третий счетчик используется для установки двух других. В частности, третий счетчик нужен при делении или умножении числа на г. 362 ГЛАВА 8. ВВедение В теоРию мАшин тьюРинГА Операции над магазином можно разделить на три вида: вытолкнуть верхний символ из магазина, изменить магазинный символ и поместить символ в магазин.
Переход двухмагазннной яашнны может вовлекать несколько таких операций; в частности, замену верхнего символа Л цепочкой символов нужно разделить на замену Х и затем помещение дополнительных символов в магазин. Эти операции выполняются над магазином, который представлен числом 8 сяелуюшим образом, Заметим, что лля выполнения операций, требующих подсчета чисел от О до г -1, можно использовать конечное управление мультистековой машины. !.' Для выталкивания из магазина нужно изменить! на !!гэ отбрасывая остаток, которым является Хь Начиная с нулевого значения третьего счетчика, число ! несколько раз сокращается на г, а третий счетчик увеличивается на 1. Когда счетчик, первоначально имевший значение 1, достигает О, происходит остановка. Затем исходный счетчик увеличивается на 1 и третий счетчик уменьшается на 1 до тех пор, пока третий счетчик снова не станет нулевым. В этот момент счетчик, в котором вначале было 8 содержит цг.
2. Для изменения Х на У на вершине магазина, представленного целым /, число ! увеличивается или уменьшается на небольшую величину, заведомо не больше г. Если УиХ рассматриваются как цифры, и У>Х, то ! увеличивается на У вЂ” Х; если У < Л; то! уменьшается наХ- К 3, Для помещения Х в магазин, содержащий 8 нужно поменяты на ге+ Х. Вначале умножаем 1 на г. Для этого несколько раз уменьшаем значение 1 на 1 и увеличиваем третий счетчик (который, как всегда, начинается с О) на г. Когда исходный счетчик достигнет О, в третьем счетчике будет нз Третий счетчик копируется в исходный и вновь обнуляется, как в п.
!. Наконец, исходный счетчик увеличивается на Х. Для завершения конструкции нужно инициализировать счетчики, чтобы имитировать иагазины из их начального состояния, в котором они содержат только начальный символ двухмагазинной машины. Этот шаг реализуется путем увеличения двух основных счетчиков на некоторое число от 1 до г — 1, соответствующее начальному символу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
