§3. Несколько примеров алгоритмических проблем

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

Теорема 5. Каждый из следующих вопросов разрешим.

(1)Пуст ли язык, допускаемый магазинным автоматом?

(2)Бесконечен ли такой язык?

(3)Является ли магазинный автомат праволинейным?

Доказательство. Без ограничения общности можно полагать, что магазинный автомат является совершенным. Покажем, что для ответа на перечисленные в теореме вопросы достаточно рассмотреть его (w, Лядро для w,d < 4.

1.L(M) = 0 тогда и только тогда, когда Core(M, 1,1) = 0.

2.Теорема о развитии означает, что каждое предложение магазинного автомата M получается из элемента ядра Core(M 1,1) вставлением циклов, имеющихся в элементах множества Core(M, 2,1). Таким образом, язык L(M) бесконечен тогда и только тогда, когда среди предложений множества Core(M, 2,1) есть содержащее нейтральный читающий цикл или гнездо, образованное циклами, хотя бы один из которых является читающим.

3.Заметим, что, с одной стороны, по определениям каждый праволинейны магазинный автомат является автоматом без самовставления. С другой сторо ны, существуют магазинные автоматы без самовставления, не удовлетворяющие определению праволинейного магазинного автомата. Таков, например, автомат

({Po,Pi,f}, {a}, {Zo,a}, Zo, 5, po, {/}),

который допускает множество a+; его множество 5 состоит из команд

(po, Л, Z) - (po, Za), Z Е {Zo, a}, (q,a,a) - (pi, Л), q Е {po,Pi}, pu- (/,Zo).

Таким образом, праволинейные магазинные автоматы образуют собственный подкласс автоматов без самовставления. Однако ответ на вопрос о праволиней-ности некоторого автомата M не проще, чем ответ на вопрос о том, является ли M автоматом без самовставления, так как не удается упростить схему дока зательства, представленную в разделе 1.2 выше. Пользуясь этой схемой, можно убедиться, что если недетерминированный магазинный автомат не является пра волинейным, то обнаружение этого гарантируется (4,4)ядром автомата.

Если же магазинный автомат праволинеен, то в элементах его (4,4)ядра, как и во всех его предложених, каждый открывающий читающий цикл является мо номом.

Таким образом, магазинный автомат M праволинеен тогда и только тогда, когда в предложениях ядра Core(M, 4, 4) каждый открывающий читающий цикл есть моном □

Следующее отношение эквивалентности подходит (ср. [Eilenberg 74]) для дока -зательства разрешимости проблемы эквивалентности конечных автоматов. Пусть A = (K, Tj,5,po,F) есть конечный автомат, S1,S2 С K. Множества состояний

Si,S2 назовем эквивалентными в том и только том случае, когда L(Si) = L(S2), где

L(S) = {x е Е* \ 3p е S 3/ е F pxf есть путь на Л} VS С K.

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

(1)Автомат никогда не стирает в магазине.

(2)В любом гнезде хотя бы один из парных участков не является циклом.

(3)Автомат является праволинейным.

Рассмотрим проблему экивалентности множеств вершин в случае детерминированных магазинных автоматов.

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

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

Автомат

МХи...,Хп,ylt...,yn = (K, A, T,Zo,5,ро, {/}),

где xi,..., Xn, yi,...,Vn е Е+, Zq е Е, Г = Е U {Zq}, A = Е U {a, b, c, db..., dn} есть алфавит из \Е\ + n + 3 символов, определяется следующим образом.

Пусть 1 < i < n, Z е Г, g, h е Е, wR обозначает обращение цепочки w. Тогда множество команд 5 задается следующими формулами:

1)(po, a, Zq) -> (pi, Zq),

2)(p0,b,ZQ) - (p2,Z0),

3)(p1,di,Z) - (p1,ZxR),

5)(q,g,g) - (q, л),

6)(q,c,g) - (/,g),

7)(q,g, Z0) - (r, ZQ),

8)(q,h,g) - (r,g), h =

9)(r,g,Z) - (r,Z),

10)(r,c,Z) - (/,Z),

11)(p2,di,Z) - (p2,ZyR),

12)(po,c, Zq) - (pb,Zq),

13)(p3,di,Zo) - (p4,Zq),

14)(p4, di, Zq) - (p4, Zq),

15)(p4, c, Zq) - (r, Zq).

Данный автомат допускает язык aL1 U bL2 U cL, где

L = {di,..., dn}+cЕ*c, L1 = L \ {dik... di1 cxi1 ... xikc \ k > 0, 1 < ij < n для 1 < j < k},

L2 = L \ [dik... di1 cyh ... yikc k > 0, 1 < ij < n для 1 < j < k}.

Действительно, если в начальном состоянии прочитан символ c (см. команду 12), то далее применяются команды 13-15 и 9-10, ничего не запоминающие в магазине, т.е. определяющие, по существу, детерминированный конечный автомат. Они обеспечивают переход из состояния p3 в заключительное состояние / под действием цепочки из L и только такой цепочки. Команды 1 и 2 "запускают подавтоматы", определяемые соответственно подмножествами команд {3,..., 10} и {4,..., 10,11}. Команды 3-10 допускают язык Li таким же способом, каким автомат Mx параграфа 2 допускает язык L \ Lx. Аналогично, однотипно построенные команды 11 и 4-10 допускают язык L2.

Легко видеть, что L = L1 U L2 тогда и только тогда, когда

xh ... Xik = yh ...yik V(k > 0,1 < ii,..., ifc < n).

Следовательно, множества {(p1,Z0), (p2,Z0)} и {(p3,Z0)} эквивалентны тогда и только тогда, когда отвечающий автомату случай проблемы соответствия Поста не имеет решений □

Идею, использованную в параграфе 2 для построения специальных детерминированных магазинных автоматов Mx и My, можно приспособить для доказательства неразрешимости вопроса, регулярно ли объединение двух непустых детерминированных языков. Точнее, мы докажем

Утверждение 1. Не существует алгоритма, который по любым заданным конечному автомату A и допускающим непустые языки детерминированным магазинным автоматам M1 и M2 определяет, верно ли равенство

L(Mi) U L(M2) = L(A).

Доказательство. Рассмотрим множество пар Эграфов (Dx,Dy), биективно отображающееся на множество всех случаев проблемы соответствия Поста в ал фавите {a, b}.

Пусть Е, L, Lx и Ly определены, как в параграфе 2. Эграф Dx определим как граф детерминированного магазинного автомата Mx, получаемого из Mx добавле -нием еще одного состояния gx, которое не является заключительным, и заменой команды (5) на

С0, Z0x) - (gx, Z0x).

Автомат Mx допускает язык L \ Lx.

Аналогично определим автомат My, допускающий язык L \ Ly.

Для каждой пары магазинных автоматов Mx и My рассмотрим один и тот же детерминированный конечный автомат A, допускающий язык L; он определен в параграфе 2.

Ясно, что объединение L(Dx) U L(Dy) совпадает с L тогда и только тогда, когда рассматриваемый случай проблемы соответствия Поста не имеет решений. Следо вательно, не существует алгоритма, который для произвольного случая проблемы соответствия Поста определяет, справедливо ли равенство

L(Dx) U L(Dy) = L.

Отсюда выводим истинность утверждения □