Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 81
Текст из файла (страница 81)
Пусть И<=Я> Е,Глбь<1ьВ,Р>)— МТ М,, модифицированная, как описано выше, т.е. она никогда не записывает пробел В. Построим М> = (а>, Х х [В], Гь Во <10, [В, В), Р>), компоненты которой определены следующим образом. (), — состоЯниЯми М, ЯвлЯютсЯ [>1<, <7>] [) (< > х [О, Ц), т.е. начальное <)<ь е>це одно 9, и все состояния М, со вторым компонентом (> или Л (иррег или 1ои ег — верхний или нижний).
Второй компонент указывает на дорожку, в которой находится клетка, обозреваемая М> (см. рис. 8.19), т.е. У означает, что головка М, находится в начальной позиции или справа от нее, а  — что слева. Г> — ле<почными символами являются все пары символов из Гь т.е. Г> х Г,. Входными символами М, являются пары вида [а, В), где а из Х. Пробел М< имеет пробелы в обоих компонентах.
Кроме того, для каждого символа Х из Г> в Г, есть пара [Х, *], где * — новый символ, который отсутствует в Гз и отмечает левый конец ленты Мь 8> — переходы М< определены следующим образом, 1, б<(<)<ь [а, В]) = (9ь [а, *), В) для каждого а из Е. Первый переход машины М, помещает маРкеР ' на нижнюю доРожкУ левой клетки. Состоинием становитсЯ 9ь а головка сдвигается вправо, поскольку не может двигаться влево или оставаться наместе. 2 б<(<7>, [Х В]) = ([<уь Ц [Х В), В) для каждого Х из Г,. М> в состоянии В, устанавливает начальное состояние Мь возвращая головку в начальную позицию и изменяя состояние на [<7л О], т.е. начальное состояние М> с головкой М, на первой дорожке. 3.
Еслибы,(<),Х)=(р, У,о),тодлякаждого_#_изГ> Б>([9, ()], [Х, 2]) = ([р, Ц, [У, 2), 2)) и б>([<7, Ц, [2, Х]) = ([р, В], [2, у), О), где 3 — направление, противоположное О, т.е. Л, если 0 = В, и В, если () = Л. Если М> не находится в крайней слева клетке, то она имитирует Мз на подходящей для 357 8.5. МАШИНЫ ТЬЮРИНГА С ОГРАНИЧЕНИЯМИ этого дорожке — верхней, если вторым компонентом состояния является У, и нижней — если 7.. Заметим„что, работая с нижней дорожкой, М, сдвигает головку в направлении, противоположном сдвигу головки М,.
Такой выбор направления естественен, поскольку левая половина ленты М хранится в нижней дорожке М~ в обрат- ном направлении. 4, Если бз(9,Л) = (р, У,)7), то Б~([д, Л], [Х *]) = 4([9, (/], [Х, *]) =([р, О], [У. *], )1). Это правило распространяется на один случай обработки левого концевого маркера *. Если М из начальной позиции движется вправо, то„независимо от того, была ли она раньше слева или справа от этой позиции (второй компонент состояния М, может быть как 7., так и У), М, должна двигаться вправо и обрабатывать верхнюю дорожку. Таким образом, на следующем шаге М, окажется в позиции, представ- леннойХ парис. 3.19.
5. Если бз(е), Х) = (р, У, Ь), то бз([д, Ц, [Х, *]) = 4([д, О], [Х, *]) = ([р, Ц, «У, *], )1). Это правило подобно предыдущему, но связано со случаем, когда Мз сдвигается влево от своей начальной позиции. Мз должна двигаться вправо от своего концевого маркера, но обрабатывать нижнюю дорожку, т.е. клетку, представленную Х, на рис. 3.19. р, — множеством допусканнцих состояний является г", х [(7, Ц, т.е. все состояния Мн первым компонентом которых является допускающее состояние Мь В момент допускания М~ может обрабатывать как верхнюю, так и нижнюю дорожку.
Доказательство теоремы по существу завершено. С помощью индукции по числу переходов, совершаемых М» можно заметить, что М, имитирует МО М, на своей ленте, если взять нижнюю дорожку, развернуть и дописать к ней верхнюю. Заметим также, что 8 М, попадает в одно из допускающих состояний тогда и только тогда, когда это же делает Мл Таким образом, ЦМ,) = 7.(Мз). П 8.5.2, Мультистековые машины Теперь рассмотрим несколько вычислительных моделей, основанных на обобщениях магазинных автоматов. Вначале рассмотрим, что происходит, если МП-автомат имеет несколько магазинов.
Из примера 3.7 уже известно, что МТ может допускать языки, не допускаемые никаким МП-автоматом с одним магазином. Однако оказывается, что есди снабдить МП-автомат лвумя магазинами, то он может допустить любой язык, допускаемый МТ. Рассмотрим также класс машин, называемых "счетчиковыми машинами'*. Они обладают возможностью запоминать конечное число целых чисел ("счетчиков") и совершать в Не забудем и о е, которую нужно удалить.
— Прим. перев. 338 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА различные переходы в зависимости от того, какие из счетчиков равны О (если таковые вообще есть). Счетчиковая машина может только прибавить 1 к счетчику или вычесть 1 вз него, но отличить значения двух различных ненулевых счетчиков она не способна, Следовательно, счетчик похож на магазин с двухсимвольиым алфавитом, состоящим из маркера дна (он появляется только на дне) и еше одного символа, который можно заносить в магазин и выталкивать из него. Вход Допустить/отвергнуть Рис.
8.20. Л4ашаяа с тремя магаэпяалат Формальное описание работы мультистековой, или многомагазинттай машины здесь ве приводится, но идея иллюстрируется рис. 8.20; ут-магазинная машина представляет собой детерминированный МП-автомат с т1 магазинами, Он получает свои входные данные, как и МП-автомат, из некоторого их источника, а не с ленты или из магазина, как МТ. Мультистековая машина имеет конечное управление, т.е. конечное множество состояний, и конечный магазинный алфавит, используемый для всех магазинов. Переход мультистековой машины основывается на состоянии, входном символе и верхних символах всех магазинов. Мультистековая машина может совершить г-переход, не используя входной символ, но лля того, чтобы машина была детерминированной, в любой ситуации не должно быть возможности выбора в-перехода или перехода по символу. За один переход мультистековая машина может изменить состояние и заменить верхний символ в каждом из магазинов цепочкой из нуля или нескольких магазинных символов.
Обычно для каждого магазина бывает своя замешающая цепочка. Итак, типичное правило перехода для к-магазинной машины имеет вид фу, а,Хт,Х, ...,Хл) = (р, уэ, уг, ..., уь). Его смысл состоит в том, что, находясь в состоянии г), с Х, на вершине Ьго магазина, 1= 1, 2, ..., т1, машина может прочитать на входе а (либо символ алфавита, либо г), перейти в состояние р и заменить Х, на вершине Ьго магазина цепочкой у, т'= 1, 2, ..., тт. Мультистековая машина допускает, попав в заключительное состояние. 8.5.
МАШИНЫ ТЬЮРИНГА С ОГРАНИЧЕНИЯМИ Добавим одно свойство, которое упрощает обработку входа описанной детерминированной машиной. Будем предполагать, что есть специальный символ 5, называемый конНевым маркероч (маркером конца входа), который встречается только в конце входа и не является его частью. Присутствие маркера позволяет узнать, когда прочитан весь доступный вход. В локазательстве следующей теоремы будет показано, каким образом концевой маркер облегчает имитацию машины Тьюринга на мультистековой машине. Заметим, что обычная МТ не нуждается в спепиальном маркере конца, поскольку в этой роли выступает первый пробел.
Теорема 8ЛЗ. Если язык Т, допускается машиной Тьюринга, то Ь допускается лвухмагазинной машиной. Доказательство. Основная идея состоит в том, что лва магазина могут имитировать одну ленту машины Тьюринга, причем один магазин хранит содержимое ленты слева от головки, а второй — то, что находится справа, за исключением бесконечных цепочек пробелов, окружающих значащие символы ленты. Более детально, пусть Т, есть ЦМ) для некоторой (одноленточной) МТ М. Наша двухмагазинная машина Я выполняет следующие действия. 1, Я начинает с маркером дпа в каждом из магазинов.
Этот маркер может быть стартовым символом лля магазинов и не должен появляться больше нигде в магазине, В дальнейшем будем говорить, что "магазин пуст", когда он содержит лишь маркер дна. 2. Пусть иб является входом Я. Ь' копирует и в первый магазин, прекращая копирование, прочитав маркер конца входа. 3. о выталкивает каждый символ по очереди из первого магазина и помешает его во второй магазин. Теперь первый магазин пуст, а второй содержит и с ее левым кон- цом на вершине.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
