T = ToTiT2T3, где Ti - нейтральный или накапливающий цикл, lo(TiT2) = Л (участок T2 может быть пустым), T2T3 не содержит нейтрального или накапливающего цикла с пустой пометкой. Ввиду леммы 1 Ti = T2T3T4 для некоторого маршрута T4. Следовательно, маршрут T2T3 является нейтральным или накапливающим как начальный участок нейтрального или накапливающего маршрута Ti. Это означает, что никакая подцепочка зарядов p(Ti) и p(T2T3) не является парной какойлибо подцепочке заряда p(To). Но тогда для любого k > 0 ToTkT2T3 есть предложение и, таким образом, M имеет зацикливающую конфигурацию □ Пусть

G = (K, Е, T,Zo,V,E,po,F)

есть граф вида, определенного в начале первого раздела, f е K. Тогда обозначим через

Automaton(G)

магазинный автомат (K U {f}, Е, Г, Z0, {rule(n) п е E} U {(p, Л, Z) -> (f, Z) (p, Z) е Fin, ЗХ е Г (p,X) е V - Fin}, po, {p е K 3Z е Г (p, Z) е Fin; VX е Г (p,X) е V - Fin} U {f}). Заметим, что

ExtG(Automaton(ExtG(M))) = ExtG(M).

Следующий алгоритм фактически устраняет зацикливающие конфигурации успешных вычислений ДМА.

Алгоритм 1. Устранение нечитающих концевых циклов.

Вход. ДМА M = (K, Е, Г, Zo, 5,Po, F).

Выход. G = (K, Е, Г, Zo, V, E, po, Fin).

Метод. E := {п е E(M) любой T е C+(M) не содержит дуги п};

V := {P е V(M) Зп е E : вершина P инцидентна дуге п} U {Po(M)};

Fin := V П [Fin(M) U{P P является вершиной некоторого цикла из C+(M)}].

В следующей теореме используются обозначения алгоритма 1.

Теорема 1. Если M - ДМА, то:

1)M = Automaton(G) является детерминированным;

2)L(M) = L(M); 3) M не имеет зацикливающих конфигураций.

Доказательство. 1. Заметим, что алгоритм 1 дает значение E С E(M). Но в подмножестве множества дуг детерминированного магазинного автомата свойство детерминированности сохраняется. Рассмотрим нечитающие нейтральные дуги, которые может добавить операция Automaton. Начальная вершина P такой ду ги в исходном автомате является начальной вершиной некоторых нечитающих дуг, удаляемых алгоритмом 1. В новом автомате P остается начальной вершиной единственной нечитающей дуги. Таким образом, операция Automaton не вносит недетерминированности.

2. Из доказательства леммы 2 имеем, что если предложение ДМА содержит нечитающий нейтральный или накапливающий цикл, то любая дуга следующего за этим циклом участка совпадает с некоторой его дугой. Таким образом, предложение автомата M имеет вид TTгде T не содержит дуг циклов из C+(M), а T либо пуст, либо каждая его дуга есть дуга некоторого цикла из C+(M). В автомате M маршруту TT отвечает в первом случае маршрут T = TT, а во

втором случае маршрут T(p, Z)Л(/, Z), если end(T) = (p, Z) и p £ F, или просто T, если p £ F. Отсюда следует равенство языков L(M) и L(M).

3. Из конструкции автомата M получаем равенство C+(M) = 0. По лемме 2 M не имеет зацикливающих конфигураций □

Пример 1. Магазинный автомат с заключительным состоянием p и следующими командами допускает язык {а}:

1)(po,a,Zo) - (po,Zoa),

2)(po, Л, а) - (p, aZ),

3)(p, K,Z) - (po, Л). Соответствующий автомату граф имеет три дуги:

(p0,Z0) - (p0,a), (p0),a) - (p,Z), (p,Z )(po,a)-

После устранения нечитающих концевых циклов остается только первая из них. Ее конечная вершина становится заключительной, но состояние, входящее в состав этой вершины, не является заключительным состоянием исходного автомата. Состояние po нельзя объявить заключительным: результирующий граф будет определять язык {Л, а} вместо исходного. Операция Automaton добавляет новое состояние / и новую команду

(po, Л а) - (/, а)

и тем решает проблему.

1.3. Автоматы, наполняющие магазин в реальное время

Пусть магазинный автомат M таков, что со(п) = Л для любой дуги п £ E(M). Тогда назовем M магазинным автоматом реального времени (МАРВ). Будем также говорить, что M действует в реальное время.

Утверждение 1. Языки, допускаемые детерминированными МАРВ, составляют собственный подкласс детерминированных языков □

Для доказательства достаточно указать пример детерминированного языка, не допускаемого никаким детерминированным МАРВ (ДМАРВ). Таков язык

{ambnam m, n > 0} U {ambncbnam m, n > 0}

(см. [Ginsburg -Greibach 66]).

Утверждение 1 означает, что детерминированных МАРВ недостаточно для описания класса детерминированных языков. Остается строить автоматы, по возмож ности близкие к форме ДМАРВ.

Пусть граф

G = (K, £, r,Zo, V,E,po,Fm)

таков, что для любой дуги п £ E из равенства ш(п) = Л следует равенство /х(п) = -Z для некоторого Z из Г. Тогда назовем автомат Automaton(G) наполняющим магазин в реальное время.

Заметим, что ДАНРВ может иметь нечитающие нестирающие дуги. Но каждое предложение ДАНРВ содержит не более одной нечитающей нестирающей дуги. Такая дуга, если она есть, заканчивает предложение, как в случае ДАНРВ M =

Automaton(G) для

G = ({p}, {a,b}, r,Zo,V,E,p, {(p,X)}), где Г = {X, Y, Z, Zo}, V = {(p, W) W G Г}, множество E составлено дугами

(PZo)+Xz (P,Z), (P,Zo)Wz (P,Z), (P,Z) -Z (PX) (PZ) T-Z (P,Y). Граф ExtG(M) имеет дополнительно к дугам графа G дугу

(p,X )A(/,X).

Докажем, что детерминированный язык допускается некоторым ДАНРВ. Введем обозначение

E+(M) = {п G E(M) ш(тг) = A, 37 G Г* ц(тг) = +Y}.

Если G - граф, эквивалентный M, то наряду с обозначением E+ (M) будем использовать обозначение E+(G).

Пусть п G E(M). Тогда назовем множество маршрутов

adj(п) = { {end(n)}, Дп G E(M) : end(n) = Ъед(п), j( ) у {п G E(M)end(n) = Ъед(п)} в противном случае

множеством соседей дуги п.

Заметим, что если п G adj(п), то пп не обязательно является маршрутом. Так, в графе, содержащем дуги

п = (p, Z) -Z (q,Y),

п1 = (qi,X )+Z (pZ)j

(p,Z) -Z (q,X), (q2,Y )+Z (p,Z),

дуга принадлежит множеству adj( 1), но 1 не является маршрутом.

Пусть e G E+ (M), T G adj(e). Тогда назовем вычеркиванием функцию e(e,T), определяемую следующим образом: если T - пустой маршрут, то

e(e,T) = Ъед(б),

e(e,T) = Ъед(б) , ((T\ ., end(T).

Алгоритм 2. Устранение нечитающей нестирающей дуги. Вход. Магазинный автомат

M = (K, Е, r,Zo,po,F)

б G E+(M).

Выход. Граф Eps(ExtG(M= (K, Е, Г, Zo, V, E, po, Fin).