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

Лемма 3. Язык успешных маршрутов Dграфа является детерминированным языком реального времени.

Доказательство. Рассмотрим произвольный Dграф

D = (£, V, P, Л, Po, F).

Модифицируем алгоритм 2 главы 1 так, чтобы его выходом был магазинный авто -мат, допускающий не L(D), а Sentences(D). Для этого достаточно использовать саму дугу там, где алгоритм использовал ее пометку.

Обозначим автомат над алфавитом E(D), производимый данным модифициро -ванным алгоритмом, через Super(D).

Из конструкции автомата Super(D) следует, что он является детерминирован -ным и что каждая его команда читает символ входного алфавита □

Заметим, что равносильными лемме 3 являются утверждения "язык успешных маршрутов магазинного автомата является детерминированным языком реального времени "и "пересечение подмножества D языка с локальным множеством явля ется детерминированным языком реального времени".

Лемма 4. Для любого бесконтекстного языка L существует преобразователь с магазинной памятью S, согласованный с некоторым детерминированным магазин ным автоматом M, действующим в реальное время, и такой, что S(L(M)) = L.

Доказательство. По доказанному в главе 1 бесконтекстный язык L опреде ляется некоторым D графом D. Из доказательства леммы 3 следует, что язык Sentences(D) = L(Super(D)) допускается некоторым детерминированным мага -зинным автоматом M, действующим в реальное время. Рассмотрим согласован ный с автоматом M преобразователь MetaD с магазинной памятью, который со -ответственно входному символу п (дуге исходного Dграфа) пишет на выходной ленте символ ш(п). Тогда

MetaD (L(M)) = L(D) = L

□

Отметим теперь, что Dграфы Di и D2 эквивалентны тогда и только тогда, когда

MetaDl (L(Super(D1))) = MetaD2 (L(Super(D2))),

и что язык, определяемый D графом D, регулярен тогда и только тогда, когда регулярен язык

MetaD(L(Super(D))).

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

§4. О магазинных автоматах с одним поворотом, действующих в реальное время

В данной главе развита теория Эграфов, которые отвечают действующим в реальное время магазинным автоматам с одним поворотом. Пусть

D = (Е, V, P, Л, Po, F)

есть граф данного класса. Пусть

Turn = {P G V Э(тг1 G Left(P),п2 Е Right(P))

end (pi 1) = beg(pi2) = P}.

Менее формально, в Turn входит общая вершина двух дуг, образующих нейтральный маршрут.

Графу D можно сопоставить два конечных автомата:

Push(D) = ({beg(n),end(n) п G Left(P)}, Е, Left(P), p0, Turn)

Pop(D) = ({beg(n),end(n) п G Right(P)}, Е, Right(P), F, Turn).

Язык L(Push(D)) включает в себя множество цепочек, прочитываемых соответствующим графу магазинным автоматом до "поворота", т. е. перехода от накопления в магазине к стиранию. L(Pop(D)) включает множество обращений цепочек, прочитываемых после поворота. Механизм зарядов маршрутов позволя ет выбрать из L(Push(D)) и L(Pop(D)) пары (x, y) цепочек, таких, что сцепления xyR образуют язык L(D). (Здесь yR обозначает обращение цепочки у.)

Обозначим через M класс всех совершенных магазинных автоматов, действующих в реальное время (СМАРВ), а через M1 класс всех СМАРВ с одним по -воротом. Описанное наблюдение приводит к мысли применить для исследования автоматов из M1 методы и приемы, разработанные для конечных автоматов. В [Eilenberg 74] особенно тщательно и полно изложены касающиеся конечных ав -томатов результаты, полученные на алгебраической основе. Множество Q состо -яний (или вершин) детерминированного конечного автомата, допускающего неко торое подмножество множества £*, названо в [Eilenberg 74] правым Емодулем. На множестве Q задаются "действия"частичной функцией © : Q х Е* -> Q. Эта функция получается чисто алгебраическим расширением частичной функции Q х Е - Q, которая определяет дуги рассматриваемого конечного автомата. В терминах действий изящно доказывается, например, разрешимость проблемы эквивалентности конечных автоматов.

Здесь мы обобщаем указанную технику в целях исследования автоматов из M1. Если по [Eilenberg 74] действие определяет некоторый путь в конечном автомате, то в нашем случае действие определяет два парных маршрута T1 и T2, переводя пару вершин

(beg(T1 ), end(T2))

(end(T1), beg(T2)).

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

M = (K, Е, r,Zc,5,po,F)

есть автомат из M1. Пусть V(M) - множество вершин автомата M, R(M) = V(M) х V(M); Е( = Left(P(M)), Е) = Right(V(M)).

Так как автомат M является совершенным, любое его предложение является цепочкой Эязыка над Эмножеством P(M).

Ф = {(s,t) G Е* х Е* s = t}. Обозначим через е элемент (Л, Л) G Ф. Определим на Ф умножение следующим образом. Пусть фг = (sj, ti) G Ф для i = 1, 2. Тогда

ф2 = (SiS2,t2ti).

(Заметим, что Ф является моноидом с единицей е.)

В следующем определении X, X1, X2 С R(M); а1, а2 G Е; P1, P2, Q1, Q2 G V(M); ф, ф1, ф2 G Ф.

Определим функцию

Am : 2R(M) х Ф 2R(M), которая задает действия на множестве всех подмножеств пар вершин автомата M G M1, таким образом:

Am (Am (X, Ф1), Ф2) = Am (X, Ф1Ф2), Am (X,e)= X,

Am(X1UX2, ф) = Am(X1, ф) U Am(X2, ф), Am (0,ф) = 0,

Am({(P1,Q2)}, («1,02)) = {(Q1 ,P2) 1 Э(тг1,7Г2) G P(M): для i = 1,2=

aj, beg(nj) = Pj, end(nj) = Qj}.

Для сокращения записи применим следующие обозначения. Пусть X, Y С R(M), ф = (s1, s2) G Ф, Y = Am(X, ф). Тогда запишем Y = Xф и Y = X(s1, s2). Если X = {(P1,P2)}, то будем применять также запись Y = (P1s1, s2P2).

Из данного определения видно, что функция Am определяется множеством P(M). Согласно следующей лемме, это множество совпадает со множеством

Pcore(M) = {(ТГЬ7Г2) G Е( X Е) 1

дуги п1 и п2 парны в некотором предложении из Core(M, 1,1)}. Таким образом, определение функции Am является конструктивным.

Лемма 5. Пусть T = T0n1T1n2T2 - предложение совершенного магазинного автомата M. Пусть дуги п1 и п2 парны в T. Тогда найдется предложение T" = TOn1T1n2T2GCore(M), в котором дуги п1, п2 парны.

Доказательство. Заметим, что маршрут T1 нейтрален, так как дуги п1 и п2 парны.