dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 74
Текст из файла (страница 74)
Это ограничение не изменяет того, что могут вычислитьмашины Тьюринга, поскольку любая последовательность переходов с остающейся наместе головкой и последующим сдвигом может быть сжата до одного перехода с изменением состояния и ленточного символа и сдвигом головки влево или вправо.Формальная запись, используемая для машин Тьюринга (МТ), похожа на запись конечных автоматов или МП-автоматов. МТ описывается семеркойM = (Q, Σ, Γ, δ, q0, B, F),компоненты которой имеют следующий смысл.Q — конечное множество состояний конечного управления.Σ — конечное множество входных символов.Γ — множество ленточных символов; Σ всегда есть подмножество Γ.δ — функция переходов.
Аргументами δ(q, X) являются состояние q и ленточный символX, а значением, если оно определено, — тройка (p, Y, D). В этой тройке p есть следующее состояние из Q, Y — символ из Γ, который записывается вместо символа вобозреваемой клетке, а D — направление сдвига головки “влево” или “вправо”, обозначаемое, соответственно, как L или R.q0 — начальное состояние из Q, в котором управление находится в начале.B — пустой символ, или пробел. Этот символ принадлежит Γ, но не Σ, т.е. не являетсявходным. Вначале он записан во всех клетках, кроме конечного их числа, где хранятся входные символы.
Остальные символы называются значащими.F — множество заключительных, или допускающих, состояний; является подмножеством Q.8.2.3. Êîíôèãóðàöèè ìàøèí ÒüþðèíãàДля формального описания работы машины Тьюринга нужно построить систему записи конфигураций, или мгновенных описаний (МО), подобную нотации, определеннойдля МП-автоматов.
Поскольку МТ имеет неограниченно длинную ленту, можно подумать, что конечное описание конфигураций МТ невозможно. Однако после любого конечного числа шагов МТ может обозреть лишь конечное число клеток, хотя и ничем неограниченное. Таким образом, в любом МО есть бесконечный префикс и бесконечныйсуффикс из клеток, которые еще не обозревались. Все эти клетки должны содержать илипробелы, или входные символы из конечного их множества.
Таким образом, в МО вклю8.2. ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀСтр. 331331чаются только клетки между крайними слева и справа значащими символами. В отдельных случаях, когда головка обозревает один из пробелов перед или за участком значащих символов, конечное число пробелов также включается в МО.Кроме ленты, нужно представить конечное управление и позицию головки. Для этогосостояние помещается непосредственно слева от обозреваемой клетки. Во избежание неоднозначности получаемой цепочки, состояния обозначаются символами, отличными отленточных.
Таким образом, для представления МО используется цепочка X1X2…Xi–1qXiXi+1…Xn. Здесь q — состояние МТ, головка обозревает i-ю слева клетку, а X1X2…Xnпредставляет собой часть ленты между крайними слева и справа значащими символами.Как исключение, если головка находится слева или справа от значащих символов, некоторое начало или окончание X1X2…Xn пусто, а i имеет значение, соответственно, 1 или n.Переходы МТ M = (Q, Σ, Γ, δ, q0, B, F) описываются с помощью отношения |− , исMпользованного для МП-автоматов. Подразумевая МТ M, для отображения переходов используем |− .
Как обычно, для указания нуля или нескольких переходов МТ M использу**ется отношение |− или |− .MПусть δ(q, X) = (p, Y, L), т.е. головка сдвигается влево. ТогдаX1X2…Xi–1qXiXi+1…Xn |− X1X2…Xi–2pXi–1YXi+1…Xn.MЗаметим, как этот переход отображает изменение состояния на p и сдвиг головки наклетку i – 1. Здесь есть два важных исключения.Если i = 1, то M переходит к пробелу слева от X1. В этом случае1.qX1X2…Xn |− pBYX2…Xn.MЕсли i = n и Y = B, то символ B, заменяющий Xn, присоединяется к бесконечной последовательности пробелов справа и не записывается в следующем МО.
Таким образом,2.X1X2…Xn–1qXn |− X1X2…Xn–2pXn–1.MПусть теперь δ(q, X) = (p, Y, R), т.е. головка сдвигается вправо. ТогдаX1X2…Xi–1qXiXi+1…Xn |− X1X2…Xi–1YpXi+1…Xn.MЭтот переход отражает сдвиг головки в клетку i + 1. Здесь также есть два важных исключения.1.Если i = n, то (i + 1)-я клетка содержит пробел и не является частью предыдущегоМО. Таким образом,X1X2…Xn–1qXn |− X1X2… Xn–1YpB.M2.Если i = 1 и Y = B, то символ B, записываемый вместо X1, присоединяется к бесконечнойпоследовательности пробелов слева и опускается в следующем МО. Таким образом,qX1X2…Xn |− pX2…Xn.M332Стр.
332ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀПример 8.2. Построим машину Тьюринга и посмотрим, как она ведет себя на типичном входе. Данная машина Тьюринга будет допускать язык {0n1n | n ≥ 1}. Изначально наее ленте записана конечная последовательность символов 0 и 1, перед и за которыми находятся бесконечные последовательности пробелов. МТ попеременно будет изменять 0на X и 1 на Y до тех пор, пока все символы 0 и 1 не будут сопоставлены друг другу.Более детально, начиная с левого конца входной последовательности, МТ цикличноменяет 0 на X и движется вправо через все символы 0 и Y, пока не достигнет 1. Она меняет 1 на Y и движется вправо через все символы Y и 0, пока не найдет X.
В этот моментона ищет 0 непосредственно справа и, если находит, меняет его на X и продолжает процесс, меняя соответствующую 1 на Y.Если непустой вход не принадлежит 0*1*, то МТ рано или поздно не сможет совершитьследующий переход и остановится без допускания. Однако если она заканчивает работу, изменив все символы 0 на X в том же цикле, в котором она изменила последнюю 1 на Y, то еевход имеет вид 0n1n, и она его допускает.
Формальным описанием данной МТ являетсяM = ({q0, q1, q2, q3, q4}, {0, 1}, {0, 1, X, Y, B}, δ, q0, B, {q4}),где δ представлена в таблице на рис. 8.9.Состояние01СимволXYBq0(q1, X, R)——(q3, Y, R)—q1(q1, 0, R) (q2, Y, L)—(q1, Y, R)—q2(q2, 0, L)—(q0, X, R) (q2, Y, L)—q3———q4———(q3, Y, R) (q4, B, R)——Рис. 8.9. Машина Тьюринга, допускающая {0n1n | n ≥ 1}В процессе вычислений M часть ленты, на которой побывала ее головка, всегда содержит последовательность символов, описываемую регулярным выражением X*0*Y*1*.
Такимобразом, там есть последовательность символов X, заменивших 0, за которыми идут символы 0, еще не измененные на X. Затем идут символы Y, заменившие 1, и символы 1, ещене замененные Y. За этой последовательностью еще могут находиться символы 0 и 1.Состояние q0 является начальным, и в него же переходит M, возвращаясь к крайнемуслева из оставшихся символов 0. Если M находится в состоянии q0 и обозревает 0, то в соответствии с правилами (см. рис.
8.9) она переходит в состояние q1, меняет 0 на X и сдвигается вправо. Попав в состояние q1, M продолжает движение вправо через все символы 0 иY. Если M видит X или B, она останавливается (“умирает”). Однако, если M в состоянии q1видит 1, она меняет ее на Y, переходит в состояние q2 и начинает движение влево.8.2. ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀСтр. 333333Находясь в состоянии q2, M движется влево через все символы 0 и Y. Достигая крайнего справа X, который отмечает правый конец блока нулей, измененных на X, M возвращается в состояние q0 и сдвигается вправо.
Возможны два случая.1.Если M видит 0, то она повторяет описанный только что цикл.2.Если же M обозревает Y, то она уже изменила все нули на X. Если все символы 1 заменены Y, то вход имел вид 0n1n, и M должна допускать. Таким образом, M переходит в состояние q3 и начинает движение вправо по символам Y.
Если первым после Yпоявляется пробел, то символов 0 и 1 было поровну, поэтому M переходит в состояние q4 и допускает. Если же M обнаруживает еще одну 1, то символов 1 слишкоммного, и M останавливается, не допуская. Если M находит 0, то вход имеет ошибочный вид, и M также ”умирает”.Приведем пример допускающего вычисления M на входе 0011. Вначале M находитсяв состоянии q0, обозревая 0, т.е. начальное МО имеет вид q00011. Полная последовательность переходов образована следующими МО.q00011 |− Xq1011 |− X0q111 |− Xq20Y1 |− q2X0Y1 |−Xq00Y1 |− XXq1Y1 |− XXYq11 |− XXq2YY |− Xq2XYY |−XXq0YY |− XXYq3Y |− XXYYq3B |− XXYYBq4BРассмотрим поведение M на входе 0010, который не принадлежит допускаемому языку.q00010 |− Xq1010 |− X0q110 |− Xq20Y0 |− q2X0Y0 |−Xq00Y0 |− XXq1Y0 |− XXYq10 |− XXY0q1BЭто поведение похоже на обработку входа 0011 до МО XXYq10, где M впервые обозревает последний 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
