dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 80
Текст из файла (страница 80)
слева от начальной позиции головки вообще нет клеток. В следующей теореме приводится конструкция, показывающая, что МТ с односторонней лентой может имитировать обычнуюМТ с бесконечной в обе стороны лентой.В основе этой конструкции лежит использование двух дорожек на одностороннейленте. Верхняя дорожка представляет клетки исходной МТ, находящиеся справа от начальной позиции, и ее саму.
Нижняя дорожка представляет позиции слева от начальной,но в обратном порядке. Точное упорядочение показано на рис. 8.19. Верхняя дорожкапредставляет клетки X0, X1, …, где X0 — начальная позиция головки, а X1, X2, … — клетки справа от нее. Клетки X–1, X–2, и последующие представляют клетки слева от начальной позиции. Обратите внимание на * в левой клетке на нижней дорожке. Этот символслужит концевым маркером и предохраняет головку односторонней ленты от случайноговыхода за левый конец ленты.X0X1X2…*X–1X–2…Рис. 8.19. Односторонняя лента может имитировать двустороннюю бесконечную ленту356Стр. 356ÃËÀÂÀ 8.
ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀМожно усилить ограничение нашей машины Тьюринга, чтобы она никогда не записывала пробелов. Это простое ограничение, вместе с лентой, бесконечной только в однусторону, означает, что лента всегда представляет собой префикс из непустых символов,за которым следует бесконечная последовательность пробелов. Кроме того, крайнийслева непустой символ всегда находится в начальной позиции ленты.
В теоремах 9.19 и10.9 будет видно, насколько полезно предполагать, что МО имеют именно такой вид.Теорема 8.12. Каждый язык, допускаемый МТ M2, допускается также МТ M1 со следующими ограничениями.1.Головка M1 никогда не смещается влево от своей начальной позиции.2.M1 никогда не записывает пробелы.Доказательство. Условие 2 обосновать легко. Введем новый ленточный символ B′,выполняющий роль пробела, но отличный от него. Таким образом, если M2 имеет правило δ2(q, X) = (p, B, D), изменим его на δ2(q, X) = (p, B′, D).
Положим δ2(q, B′) для любогосостояния q равным δ2(q, B).Условие 1 требует больших усилий. ПустьM2 = (Q2, Σ, Γ2, δ2, q2, B, F2) —МТ M2, модифицированная, как описано выше, т.е. она никогда не записывает пробел B.ПостроимM1 = (Q1, Σ × {B}, Γ1, δ1, q0, [B, B], F1),компоненты которой определены следующим образом.Q1 — состояниями M1 являются {q0, q1} U (Q2 × {U, L}), т.е. начальное q0, еще одно q1 ивсе состояния M2 со вторым компонентом U или L (upper или lower — верхний илинижний). Второй компонент указывает на дорожку, в которой находится клетка,обозреваемая M2 (см. рис. 8.19), т.е. U означает, что головка M2 находится в начальной позиции или справа от нее, а L — что слева.Γ1 — ленточными символами являются все пары символов из Γ2, т.е. Γ2 × Γ2.
Входнымисимволами M1 являются пары вида [a, B], где a из Σ. Пробел M1 имеет пробелы вобоих компонентах. Кроме того, для каждого символа X из Γ2 в Γ1 есть пара [X, *],где * — новый символ, который отсутствует в Γ2 и отмечает левый конец ленты M1.δ1 — переходы M1 определены следующим образом.1.δ1(q0, [a, B]) = (q1, [a, *], R) для каждого a из Σ. Первый переход машины M1 помещаетмаркер * на нижнюю дорожку левой клетки. Состоянием становится q1, а головкасдвигается вправо, поскольку не может двигаться влево или оставаться на месте.2.δ1(q1, [X, B]) = ([q2, U], [X, B], L) для каждого X из Γ2.
M1 в состоянии q1 устанавливает начальное состояние M2, возвращая головку в начальную позицию и изменяя состояние на [q2, U], т.е. начальное состояние M2 с головкой M1 на первой дорожке.8.5. ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ Ñ ÎÃÐÀÍÈ×ÅÍÈßÌÈСтр. 357357Если δ2(q, X) = (p, Y, D), то для каждого Z из Γ23.δ1([q, U], [X, Z]) = ([p, U], [Y, Z], D) иδ1([q, L], [Z, X]) = ([p, L], [Z, Y], D ),где D — направление, противоположное D, т.е. L, если D = R, и R, если D = L. ЕслиM1 не находится в крайней слева клетке, то она имитирует M2 на подходящей дляэтого дорожке — верхней, если вторым компонентом состояния является U, и нижней — если L.
Заметим, что, работая с нижней дорожкой, M1 сдвигает головку в направлении, противоположном сдвигу головки M2. Такой выбор направления естественен, поскольку левая половина ленты M2 хранится в нижней дорожке M1 в обратном направлении.Если δ2(q, X) = (p, Y, R), то4.δ1([q, L], [X, *]) = δ1([q, U], [X, *]) =([p, U], [Y, *], R).Это правило распространяется на один случай обработки левого концевого маркера *. Если M2 из начальной позиции движется вправо, то, независимо от того, былали она раньше слева или справа от этой позиции (второй компонент состояния M1может быть как L, так и U), M1 должна двигаться вправо и обрабатывать верхнююдорожку. Таким образом, на следующем шаге M1 окажется в позиции, представленной X1 на рис.
8.19.Если δ2(q, X) = (p, Y, L), то5.δ1([q, L], [X, *]) = δ1([q, U], [X, *]) = ([p, L], [Y, *], R).Это правило подобно предыдущему, но связано со случаем, когда M2 сдвигается влевоот своей начальной позиции. M1 должна двигаться вправо от своего концевого маркера, но обрабатывать нижнюю дорожку, т.е. клетку, представленную X-1 на рис. 8.19.F1 — множеством допускающих состояний является F2 × {U, L}, т.е. все состояния M1,первым компонентом которых является допускающее состояние M2. В момент допускания M1 может обрабатывать как верхнюю, так и нижнюю дорожку.Доказательство теоремы по существу завершено.
С помощью индукции по числу переходов, совершаемых M2, можно заметить, что M1 имитирует МО M2 на своей ленте, если взять нижнюю дорожку, развернуть и дописать к ней верхнюю.8 Заметим также, чтоM1 попадает в одно из допускающих состояний тогда и только тогда, когда это же делаетM2. Таким образом, L(M1) = L(M2).
8358Стр. 358Не забудем и о *, которую нужно удалить. — Прим. перев.ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ8.5.2. Ìóëüòèñòåêîâûå ìàøèíûТеперь рассмотрим несколько вычислительных моделей, основанных на обобщениях магазинных автоматов. Вначале рассмотрим, что происходит, если МП-автомат имеет несколько магазинов. Из примера 8.7 уже известно, что МТ может допускать языки, не допускаемые никаким МП-автоматом с одним магазином. Однако оказывается, что если снабдитьМП-автомат двумя магазинами, то он может допустить любой язык, допускаемый МТ.Рассмотрим также класс машин, называемых “счетчиковыми машинами”. Они обладают возможностью запоминать конечное число целых чисел (“счетчиков”) и совершатьразличные переходы в зависимости от того, какие из счетчиков равны 0 (если таковыевообще есть). Счетчиковая машина может только прибавить 1 к счетчику или вычесть 1из него, но отличить значения двух различных ненулевых счетчиков она не способна.Следовательно, счетчик похож на магазин с двухсимвольным алфавитом, состоящим измаркера дна (он появляется только на дне) и еще одного символа, который можно заносить в магазин и выталкивать из него.ВходКонечноеуправлениеДопустить/отвергнутьРис.
8.20. Машина с тремя магазинамиФормальное описание работы мультистековой, или многомагазинной машины здесьне приводится, но идея иллюстрируется рис. 8.20; k-магазинная машина представляет собой детерминированный МП-автомат с k магазинами. Он получает свои входные данные,как и МП-автомат, из некоторого их источника, а не с ленты или из магазина, как МТ.Мультистековая машина имеет конечное управление, т.е. конечное множество состояний, и конечный магазинный алфавит, используемый для всех магазинов.
Переход мультистековой машины основывается на состоянии, входном символе и верхних символахвсех магазинов.Мультистековая машина может совершить ε-переход, не используя входной символ,но для того, чтобы машина была детерминированной, в любой ситуации не должно бытьвозможности выбора ε-перехода или перехода по символу.8.5. ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ Ñ ÎÃÐÀÍÈ×ÅÍÈßÌÈСтр.
359359За один переход мультистековая машина может изменить состояние и заменить верхний символ в каждом из магазинов цепочкой из нуля или нескольких магазинных символов. Обычно для каждого магазина бывает своя замещающая цепочка.Итак, типичное правило перехода для k-магазинной машины имеет видδ(q, a, X1, X2, …, Xk) = (p, γ1, γ2, …, γk).Его смысл состоит в том, что, находясь в состоянии q, с Xi на вершине i-го магазина,i = 1, 2, …, k, машина может прочитать на входе a (либо символ алфавита, либо ε), перейти в состояние p и заменить Xi на вершине i-го магазина цепочкой γi, i = 1, 2, …, k.Мультистековая машина допускает, попав в заключительное состояние.Добавим одно свойство, которое упрощает обработку входа описанной детерминированной машиной.
Будем предполагать, что есть специальный символ $, называемый концевым маркером (маркером конца входа), который встречается только в конце входа и неявляется его частью. Присутствие маркера позволяет узнать, когда прочитан весь доступный вход. В доказательстве следующей теоремы будет показано, каким образом концевой маркер облегчает имитацию машины Тьюринга на мультистековой машине. Заметим, что обычная МТ не нуждается в специальном маркере конца, поскольку в этой роливыступает первый пробел.Теорема 8.13.
Если язык L допускается машиной Тьюринга, то L допускается двухмагазинной машиной.Доказательство. Основная идея состоит в том, что два магазина могут имитироватьодну ленту машины Тьюринга, причем один магазин хранит содержимое ленты слева отголовки, а второй — то, что находится справа, за исключением бесконечных цепочекпробелов, окружающих значащие символы ленты. Более детально, пусть L есть L(M) длянекоторой (одноленточной) МТ M.
Наша двухмагазинная машина S выполняет следующие действия.1.S начинает с маркером дна в каждом из магазинов. Этот маркер может быть стартовымсимволом для магазинов и не должен появляться больше нигде в магазине. В дальнейшем будем говорить, что “магазин пуст”, когда он содержит лишь маркер дна.2.Пусть w$ является входом S. S копирует w в первый магазин, прекращая копирование, прочитав маркер конца входа.3.S выталкивает каждый символ по очереди из первого магазина и помещает его вовторой магазин. Теперь первый магазин пуст, а второй содержит w с ее левым концом на вершине.4.S переходит в начальное (имитируемое) состояние M.
Первый магазин S пуст, свидетельствуя о том, что у M слева от головки нет ничего, кроме пробелов. Второй магазин S содержит w, отражая тот факт, что справа от головки M находится w.5.S имитирует переход M следующим образом:360Стр. 360ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀа) S знает состояние M, скажем, q, поскольку S имитирует состояние M в своемсобственном конечном управлении;б) S знает символ X, обозреваемый головкой M; это символ на вершине второгомагазина S. Как исключение, если второй магазин содержит только маркердна, то M только что переместилась на пробел; S интерпретирует символ,обозреваемый M, как пробел;в) итак, S знает следующий переход M;г) следующее состояние M записывается в компоненте конечного управления Sвместо предыдущего состояния;д) если M меняет X на Y и сдвигается вправо, то S помещает Y в свой первыймагазин, имитируя то, что Y теперь слева от головки M.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
