Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[40]

автоматов специального вида, которые строятся по произвольному заданному случаю проблемы соответствия Поста. Оказывается, что существование алгоритма, который строит по двум таким детерминированным магазинным автоматам их граф сопряжений, означало бы также и существование алгоритма решения проблемы соответствия Поста, что противоречило бы известному факту об алгоритмической неразрешимости этой проблемы.

В разделе 1 определяется понятие графа сопряжений и доказывается теорема об алгоритмической неразрешимости проблемы построения графа сопряжений. Раздел 2 содержит модификацию рассмотренных в доказательстве этой теоремы специальных детерминированных магазинных автоматов, которая превращает их в детерминированные магазинные автоматы, действующие в реальное время (ДМАРВ) [Романовский 86]. С помощью новых специальных детерминированных магазинных автоматов доказывается, что из существования описанного в [Рома новский 86] имитатора совместной работы двух ДМАРВ следует существование алгоритма решения проблемы соответствия Поста. Построения работы [Романов ский 86], возможно, законны для некоторого подкласса ДМАРВ.

В последующих примерах магазинных автоматов удобно допускать в графе магазинного автомата дуги с пустым зарядом и с зарядом вида +X1... + Xm, где m > 1, Xj G Г для i = 1,..., m. Дуга с пустым зарядом как бы совмещает в себе две последовательные дуги, из которых первая добавляет символ в магазин, а вторая стирает этот символ. Дугу с зарядом +X1... + Xm, m > 1, можно считать сокращением последовательности дуг с зарядами +X1,..., +Xm.

2.1. Граф сопряжений. Представление дуги магазинного автомата парой ее вершин, пометкой и зарядом позволяет видеть нейтральные участки в записях маршрутов без обращения к D множеству данного автомата. В самом деле, с таким представлением дуг в маршруте дотошно протоколируется вид последова тельных конфигураций автомата (ср. пример, рассмотренный в разделе 1.1). В данном разделе удобно воспользоваться именно таким представлением дуг.

Далее для i = 1, 2

Mj = (Kj, Е, rj, Zoi, Sj, poi, Fj)

есть магазинные автоматы,

nj G E(Mj),

Pj G V(Mj),

e G (Е U{A}) x ({+,

tfj = {PePP G V(Mj)},

Ej = *j U E(Mj), £j G -E

Tj nj1 . . . njmi

есть успешный маршрут автомата M , njj - дуга для j = 1,..., mj.

Элементы множества j уподобим дугам (это "фиктивные"дуги: любой пустой участок некоторого маршрута, имеющий вершину P, может быть заменен по следовательностью (PeP)k, k > 0, фиктивных дуг) и введем для них понятия


начальной и конечной вершин:

beg(PeP) = end(PeP) = P.

Фиктивные дуги послужат для "выравнивания"сопрягаемых маршрутов.

Пусть= ш(п2). Тогда назовем упорядоченную пару (п1,п2) (M1,M2)-

биребром.

Каждую из упорядоченных пар (п1,ф2) и (ф1,п2) назовем (Mi, M2)-моноребром.

Введем общее для (M1, M2)биребер и (M1, M2)моноребер название (M1,M2)-ребра.

Граф, множество вершин которого есть V(M1) х V(M2), а множество дуг есть {((P1,P2), (Q1 ,Q2)) с весом (£ь6)(£ь6) есть (M1, M2)ребро, для i = 1, 2 beg(Ci) = Pj и end(i) = Qi}, обозначим через Union(M1, M2).

Вершину графа Union(M1,M2) назовем (M1,M2)-узлом.

Приставка (M1,M2) далее будет опускаться, если это не повлечет недоразуме -ний.

Мы ввели особые термины для вершин и дуг графа

Union(M1 ,M2),

так как эта уловка, по видимому, облегчит обсуждение данного графа наряду с графами магазинных автоматов M1, M2.

Пусть T1 и T2 - предложения автоматов M1 и M2 соответственно. Пусть co(T1) = u(T2). Тогда назовем (T1,T2)-сопряжением путь т в графе Union(M1, M2), получаемый по T1 и T2 следующими действиями:

т := [пустой путь с узлом ((роЬЗД, (Р02, Z02))];

n1 := 1; n2 := 1; (ni - счетчик дуг маршрута Ti)

пока n1 < m1 Л n2 < m2, выполнять следующее: если Uj(K1n1) = ш(п2и2),

то [т := т(п1П1 ,П2п2); n1 := n1 + 1; n2 := n2 + 1], иначе если ш(п1п1) = Л,

то [т := т(n1ni,beg(n2n2) £ beg(n2n2)); n1 := n1 + 1], иначе (в этом случае ш(п2п2) = Л) [т := т(beg(n1ni) £ beg(n1ni),П2п2); n2 := n2 + 1]; пока n1 < m1, выполнять присваивания

[т := т(mn1 ,end(T2) £ end(T2)); щ := щ + 1]; пока n2 < m2, выполнять присваивания [т := т(end(T) £ end(T),П2п2); Щ := Щ + 1].

Назовем графом сопряжений и обозначим через

Team(M1,M2)

такой подграф графа Union(M1, M2), что каждое его ребро является ребром неко торого сопряжения.

Сформулируем проблему построения графа сопряжений следующим образом:


построить алгоритм, который по произвольной паре (Mi,M2) эквивалентных магазинных автоматов получает граф Team(M1, M2).

Докажем, что данная проблема неразрешима даже в классе детерминированных магазинных автоматов, наполняющих магазин в реальное время и допускающих регулярные языки. Построим специальный класс магазинных автоматов, для которого из разрешимости проблемы построения графа сопряжений следует разрешимость проблемы соответствия Поста.

Пусть упорядоченные пары цепочек

(Xi,yi),(Хп,Уи),

где n > 1, определяют случай проблемы соответствия Поста в алфавите {a,b}. Пусть

£ = {a, b, 0} U {ci, ...,cn}

и £ = n + 3. Рассмотрим язык

L = {cip ... Ci10z0 p > 1, 1 < ij < n для j = 1,..., p, z £ {a, b}*}.

Язык L регулярен, так как он допускается конечным автоматом, определяемым следующими командами:

(qo, c) - qi, c £ {ci,cn},

(qi,c) - qi, c £ {ci,...,cn},

(qi, 0) - q2,

(q2, s) - q2, s £ {a,b},

(q2, 0) - q3.

Состояние q3 является заключительным состоянием данного конечного автомата.

Легко видеть справедливость следующих равенств: где

Lx = {cip ... ch 0xi1 ...Xip 0 p > 1, 1 < ij < n для j = 1,... ,p},

L - Lx = {cip ...cii0z0 p > 1, 1 < ij < n для j = 1,...,p,

z £ {a, b}*, z = Xii . ..Xip},

а Ly определяется аналогично языку Lx с помощью вторых элементов пар, опре деляющих случай проблемы соответствия Поста.

Пусть uR обозначает обращение цепочки u.

Определим детерминированный магазинный автомат

следующим образом.

Kx = {p0x,pix,p2x,p3x,p4x, fx}, rx = {Z0x, a, Fx = {fx},

множество 5x образовано командами следующих четырнадцати серий, в которых i = 1,... ,n, r, s £ {a, b}:

(1) (pox, ci, Zox) - (pox, ZoxXR),



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]