dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 91
Текст из файла (страница 91)
Их может быть бесконечно много, атакже, что гораздо хуже, если даже частичные решения wi1wi2…wir и xi1xi2…xir ведут крешению, разница их длин может быть сколь угодно большой.Пример 9.15. Списки, представленные на рис. 9.12, можно рассматривать как экземпляр МПСП. Однако этот экземпляр МПСП не имеет решения. Для доказательства заметим, что всякое его частичное решение начинается с индекса 1, поэтому цепочки, образующие решение, должны начинаться следующим образом.A: 1…B: 111…404Стр. 404ÃËÀÂÀ 9.
ÍÅÐÀÇÐÅØÈÌÎÑÒÜСледующим целым в решении не может быть 2 или 3, поскольку и w2, и w3 начинаются с10, и поэтому при таком выборе возникнет несоответствие в третьей позиции. Таким образом, следующий индекс должен быть 1, и получаются такие цепочки.A: 11…B: 111111…Эти рассуждения можно продолжать бесконечно. Только еще одно число 1 позволяет избежать несоответствия в решении. Но если все время выбирается индекс 1, то цепочка Bостается втрое длиннее A, и цепочки никогда не сравняются. Важным шагом в доказательстве неразрешимости ПСП является сведение МПСП кПСП. Далее будет показано, что МПСП неразрешима, путем сведения Lu к МПСП. Темсамым будет доказана неразрешимость ПСП.
Действительно, если бы она была разрешима, то можно было бы решить МПСП, а следовательно, и Lu.По данному экземпляру МПСП с алфавитом Σ соответствующий экземпляр ПСПстроится следующим образом. Вначале вводится новый символ ∗, который помещаетсямежду символами цепочек экземпляра МПСП. При этом в цепочках списка A он следуетза символами алфавита Σ, а в цепочках списка B — предшествует им. Исключением является новая пара, которая строится по первой паре экземпляра МПСП; в этой паре естьдополнительный символ ∗ в начале w1, поэтому она может служить началом решенияПСП. К экземпляру ПСП добавляется также заключительная пара ($, ∗$). Она служитпоследней парой в решении ПСП, имитирующем решение экземпляра МПСП.Формализуем описанную конструкцию.
Пусть дан экземпляр МПСП со спискамиA = w1, w2, …, wk и B = x1, x2, …, xk. Предполагается, что символы ∗ и $ отсутствуют в алфавите Σ данного экземпляра МПСП. Строится экземпляр ПСП со списками C = y0, y1, …,yk+1 и D = z0, z1, …, zk+1 следующим образом.1.Для i = 1, 2, …, k положим yi равной wi с символом ∗ после каждого ее символа, аzi — равной xi с символом ∗ перед каждым ее символом.2.y0 = ∗y1 и z0 = z1, т.е. нулевая пара выглядит так же, как первая, с той лишь разницей,что в начале цепочки из первого списка есть еще символ ∗.
Отметим, что нулеваяпара будет единственной парой экземпляра ПСП, в которой обе цепочки начинаютсяодним и тем же символом, поэтому всякое решение данного экземпляра ПСП должно начинаться с индекса 0.3.yk+1 = $ и zk+1 = ∗$.Пример 9.16. Пусть рис. 9.12 изображает экземпляр МПСП. Тогда экземпляр ПСП,построенный с помощью описанных выше действий, представлен на рис.
9.14. Теорема 9.17. МПСП сводится к ПСП.Доказательство. В основе доказательства лежит описанная выше конструкция. Допустим, что i1, i2, …, im — решение данного экземпляра МПСП со списками A и B; тогдаw1wi1wi2…wim = x1xi1xi2…xim. Если заменить каждую цепочку w соответствующей y и каж9.4. ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀСтр. 405405дую x — соответствующей z, то получатся две почти одинаковые цепочки y1yi1yi2…yim иz1zi1zi2…zim.
Разница между ними в том, что у первой не хватает * в начале, а у второй — вконце, т.е.*y1yi1yi2…yim = z1zi1zi2…zim*.Список CСписок Diyizi0∗1∗∗1∗1∗111∗∗1∗1∗121∗0∗1∗1∗1∗∗1∗031∗0∗∗04$∗$Рис. 9.14. Построение экземпляра ПСП по экземпляру МПСПОднако y0 = *y1 и z0 = z1, поэтому можно “расправиться” с * в начале, изменив первыйиндекс на 0:y0yi1yi2…yim = z0zi1zi2…zim*.Для учета * в конце добавим индекс k + 1.
Поскольку yk+1 = $, а zk+1 = *$, получим:y0yi1yi2…yimyk+1 = z0zi1zi2…zimzk+1.Итак, показано, что последовательность 0, i1, i2, …, im, k + 1 — решение экземпляра ПСП.Теперь докажем обратное, т.е. если построенный экземпляр ПСП имеет решение,то исходный экземпляр МПСП также имеет решение.
Заметим, что решение данногоэкземпляра ПСП должно начинаться индексом 0 и заканчиваться индексом k + 1, поскольку только в нулевой паре цепочки y0 и z0 начинаются и только в (k + 1)-й парецепочки yk+1 и zk+1 оканчиваются одним и тем же символом. Таким образом, решениеэкземпляра ПСП можно записать в виде 0, i1, i2, …, im, k + 1.Мы утверждаем, что i1, i2, …, im есть решение экземпляра МПСП.
Действительно, изцепочки y0yi1yi2…yimyk+1 можно удалить все символы * и символ $ в конце. В результатеполучим цепочку w1wi1wi2…wim. Точно так же, удалив символы * и символ $ из цепочкиz0zi1zi2…zimzk+1, получим x1xi1 xi2 …xim. Посколькуy0yi1yi2…yimyk+1 = z0zi1zi2…zimzk+1,получаем:w1wi1wi2…wim = x1xi1xi2…xim.Итак, решение экземпляра ПСП содержит в себе решение экземпляра МПСП.Теперь ясно, что конструкция, описанная перед данной теоремой, представляет собойалгоритм, который переводит экземпляр МПСП, имеющий решение, в экземпляр ПСП,406Стр. 406ÃËÀÂÀ 9.
ÍÅÐÀÇÐÅØÈÌÎÑÒÜтакже имеющий решение, а экземпляр МПСП, не имеющий решения, — в экземплярПСП, не имеющий решения. Таким образом, МПСП сводится к ПСП, а это означает, чтоиз разрешимости ПСП следовала бы разрешимость МПСП. 9.4.3. Çàâåðøåíèå äîêàçàòåëüñòâà íåðàçðåøèìîñòè ÏÑÏЗавершим цепь сведений (см. рис. 9.11), сведя Lu к МПСП. По заданной паре (M, w)строится экземпляр МПСП (A, B), имеющий решение тогда и только тогда, когда МТ Mдопускает вход w.Основная идея состоит в том, что частичные решения экземпляра МПСП (A, B) имитируют обработку входа w машиной M.
Частичные решения будут состоять из цепочек,которые являются префиксами последовательности МО M #α1#α2#α3#…, где α1 — начальное МО M при входной цепочке w и αi |− αi+1 для всех i. Цепочка из списка В всегдана одно МО впереди цепочки из списка A, за исключением ситуации, когда M попадает вдопускающее состояние. В этом случае используются специальные пары, позволяющиесписку A “догнать” список B и в конце концов выработать решение. Однако если машинане попадает в допускающее состояние, то эти пары не могут быть использованы, и проблема не имеет решения.Для того чтобы упростить построение экземпляра МПСП, воспользуемся теоремой 8.12, согласно которой можно считать, что МТ никогда не печатает пробел и ее головка не сдвигается левее исходного положения.
Тогда МО машины Тьюринга всегдабудет цепочкой вида αqβ, где α и β — цепочки непустых символов на ленте, а q — состояние. Однако тогда, когда головка обозревает пробел непосредственно справа от α,позволим цепочке β быть пустой вместо того, чтобы помещать пробел справа от состояния. Таким образом, символы цепочек α и β будут в точности соответствовать содержимому клеток, в которых записан вход, а также всех тех клеток справа, в которых головкауже побывала.Пусть M = (Q, Σ, Γ, δ, q0, B, F) — машина Тьюринга, удовлетворяющая условиям теоремы 8.12, и w — входная цепочка из Σ*.
По ним строится экземпляр МПСП следующимобразом. Чтобы понять, почему пары выбираются пары именно так, а не иначе, нужнопомнить, что нам нужно, чтобы первый список всегда на одно МО отставал от второго,если только M не попадает в допускающее состояние.1.Первая пара имеет следующий вид.Список AСписок B##q0w#В соответствии с правилами МПСП эта пара — первая в любом решении.
С нее начинается имитация M на входе w. Заметим, что в начальный момент список B опережает список A на одно полное МО.9.4. ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀСтр. 4074072.Ленточные символы и разделитель # могут быть добавлены в оба списка. ПарыСписок AСписок BXX##для каждого X из Γпозволяют “копировать” символы, не обозначающие состояния. Выбирая такие пары,можно одновременно и удлинить цепочку списка A до соответствующей цепочки спискаB, и скопировать часть предыдущего МО в конец цепочки списка B. Это поможет нам записать в конец цепочки списка B следующее МО в последовательности переходов M.3.Для имитации перехода M применяются специальные пары.
Для всех q из Q – F (т.е.состояние q не является допускающим), p из Q и X, Y, Z из Γ есть следующие пары.Список A Список BqXYpесли δ(q, X) = (p, Y, R)ZqXpZYесли δ(q, X) = (p, Y, L); Z — любой ленточный символq#Yp#если δ(q, B) = (p, Y, R)Zq#pZY#если δ(q, B) = (p, Y, L); Z — любой ленточный символКак и в пункте 2, эти пары позволяют добавить к цепочке B следующее МО, дописывая цепочку A таким образом, чтобы она соответствовала цепочке B. Однако этипары используют состояние для определения, как нужно изменить текущее МО, чтобы получить следующее. Эти изменения — новое состояние, ленточный символ исдвиг головки — отображаются в МО, которое строится в конце цепочки B.4.5.408Стр.
408Если МО, которое находится в конце цепочки B, содержит допускающее состояние,нужно сделать частичное решение полным. Для этого добавляются “МО”, которые вдействительности не являются МО машины M, а отображают ситуацию, при которойв допускающем состоянии разрешается поглощать все ленточные символы по обестороны от головки. Таким образом, если q — допускающее состояние, то для всехленточных символов X и Y существуют следующие пары.Список AСписок BXqYqXqqqYqНаконец, если допускающее состояние поглотило все ленточные символы, то оно остается в одиночестве как последнее МО в цепочке B.
Таким образом, разность цепочек (суффикс цепочки B, который нужно дописать к цепочке A для того, чтобы она соответствовала B) есть q#, и для завершения решения используется последняя пара.ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜСписок AСписок Bq###В дальнейшем пары этих пяти типов называются парами из правила 1, из правила 2и так далее.Пример 9.18. Преобразуем в экземпляр МПСП машинуM = ({q1, q2, q3}, {0, 1}, {0, 1, B}, δ, q1, B, {q3})с таблицей δqiδ(qi, 0)δ(qi, 1)δ(qi, B)q1(q2, 1, R)(q2, 0, L)(q2, 1, L)q2(q3, 0, L)(q1, 0, R)(q2, 0, R)q3———и входной цепочкой w = 01.Чтобы упростить построение, заметим, что M никогда не печатает пробел B, и его небудет ни в одном МО. Поэтому все пары с пустым символом B опускаются. Полный список пар с указанием их происхождения представлен на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
