Сформулируем следующее простое наблюдение о соответствии команд совершенного магазинного автомата его дугам; оно помогает понять конструкцию определяемого далее графа ExtG(M) и его связь с графом соответствующего автомату M совершенного магазинного автомата.

в = (р, a, Z) - (q, 7)

есть команда совершенного магазинного автомата, участвующая в его успешных вычислениях. Тогда его граф имеет дугу с начальной вершиной (р, Z), конечной вершиной (q, X) для некоторого магазинного символа X, пометкой a и зарядом а (в). Обозначим множество таких дуг через edges(e).

Пусть в - команда магазинного автомата M, не укорачивающая содержимого магазина (формально, а(в) G {-}Г). Из конструкции алгоритма совершенствования (см. алгоритм 1.1) ясно, что он сопоставляет команде в единственную упорядоченную последовательность команд

steps(e) = вг ...вк, k > 1,

которая равносильна ей по действию на состояние автомата, магазин и входную цепочку, одним словом, на конфигурацию.

Из уникальности вводимых при этом алгоритмом 1.1 состояний и магазинных символов и из отмеченного выше наблюдения следует, что ledges)! = 1 для 1 < i < k.

Обозначим через G(M) граф совершенного магазинного автомата, получаемого применением к M алгоритма 1.1.

Пусть теперь в - произвольная команда автомата M. Сопоставим ей множество Т(в) маршрутов Dграфа G(M) следующим образом:

( edges), а(в) G {-}Г, Т(в) = {пг... Пк}, а(в) {-}Г, steps) = вг ...вк, [ {п«} = edgesj) для 1 < i < k.

Определение множества Т(в) показывает осуществимость построения графа ExtG(M) с множеством вершин

V(M) = {beg(T), end(T) Зв G 5T G Т(в)}

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

E(M) = {beg(T)T)end(T) Зв G 5T G Т(в)}. p(T)

Элементы P, Q, a, w названного дугой объекта PaQ будем называть соответственно начальной вершиной, конечной вершиной, пометкой и зарядом.

Назовем входной вершиной графа ExtG(M) вершину P0(M) = (p0,Z0),за -

ключительной - каждую вершину множества Fin(M) = {(p,Z) р GF, Z G Г} П V(M). В целом ExtG(M) определяется восьмеркой

(K, Т., Г, Zo, V(M), E(M), po, Fin(M)).

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

Определенные в параграфе 1.1 понятия вычисления, маршрута, предложения и пр. без труда переносятся на случай определенных здесь графов, но мы не пытаемся определить здесь аналог Dмножества графа совершенного магазинного автомата. Используем обозначение Sentences(ExtG(M)) для множества всех предложений и определим язык L(ExtG(M)), задаваемый графом ExtG(M), формулой

L(ExtG(M)) = {lu(T) T e Sentences(ExtG(M))}.

Из конструкции графа ExtG(M) следует, что он эквивалентен графу G(M) и, значит, самому автомату M.

Далее вместо магазинного автомата M рассматривается отвечающий ему граф ExtG(M). Дуги и маршруты относятся теперь к графу ExtG(M), а не к G(M). По аналогии с названиями команд введем названия нейтральный, накапливающий, стирающий для маршрута соответственно с пустым зарядом, с зарядом +7, с зарядом -7, где 7 - непустая цепочка магазинных символов.

Нам потребуется строить магазинный автомат по графу, полученному некоторыми преобразованиями графа ExtG(M). Тогда будет полезным следующее обозначение.

п = (p,Z)-(q,X) e E(M).

Обозначим через

rule(n)

команду

9 = (p a, Z) - (q,7) e 5, где 7 e Г* определяется из равенства

fi(9) = ц(п) = w.

Из определения заряда команды следует, что заряд - и символ Z однозначно определяют цепочку 7. Следовательно, rule - это функция на множестве E(M) дуг графа ExtG(M). Доопределим функцию rule на множестве маршрутов графа ExtG( ) по правилу

rule(T) = rule(ni)... rule(nm), Т = п\.. .nm - маршрут, m > 0, п - дуга для i = 1,... ,m.

1.2. Зацикливающие конфигурации. Дугу с пустой пометкой, короче, нечи-тающую, будем обозначать буквой е.

Пусть (p,x,7) - конфигурация магазинного автомата M. Пусть для любого i > 1 существует конфигурация (pi, xi, 7), такая, что

1 7 > 7 1

(p, x, 7) =i (pi, x, 7i).

Тогда назовем конфигурацию (p, x, 7) зацикливающей конфигурацией автомата

Лемма 1. Пусть Т0Т - маршрут ДМА, Т0 - нейтральный или накапливающий цикл с пустой пометкой, Т < Т0 . Тогда Т0 = ТТ\ для некоторого маршрута Ti.

Доказательство. Применим индукцию по длине участка T. При T = 0 имеем T0 = TT0, так как вершина пустого маршрута T является конечной вершиной цикла T0 и совпадает с его начальной вершиной.

Предположим, что лемма верна, если T < m, где 0 < m < T0 , и рассмотрим случай такого маршрута T, что T = m +1. Представим T в виде T = T2n, где п - дуга. По предположению индукции T0 имеет вид T0 = T2eT3 для некоторых дуги б и маршрута T3. Вследствие детерминированности автомата и равенства со (б) = б имеем для некоторой команды 9 равенства

9 = rule(n) = rule(e)

и, следовательно,

a (9) = /(п) = /(б).

Если команда 9 не является стирающей, то она определяет единственную дугу, т.е. п = б. Допустим, что 9 - стирающая команда. Тогда а(9) = -Z для некоторого Z е Г. Стирающая команда может определять дуги, различающиеся магазинными символами своих конечных вершин. Убедимся, что рассматриваемые дуги п и б не имеют такого различия. Маршрут T26 является нейтральным или накапливающим как начальный участок нейтрального или накапливающего маршрута T0. Следовательно, ecol(T2) = +7XZ, а ecoT) = +7X для некоторых 7 е Г* и X е Г. Но тогда из равенства /(п) = /(б) вытекает, что

ecol(T2n) = /(+7XZ - Z )= +7X.

Отсюда п = б □

Обозначим через П(М) множество маршрутов без повторяющихся дуг: П(М) = {п ...пт m > 0, п е E(M)

для i = 1,..., m, пг = п при i = j}.

Из конечности множества дуг магазинного автомата следует, что для любого магазинного автомата M множество n(M) конечно. Введем обозначение C+(M) для множества циклов

{T е n(M) T - нейтральный или накапливающий цикл, co(T) = Л}.

Лемма 2. ДМА M имеет зацикливающую конфигурацию тогда и только тогда, когда C+(M) = 0.

Доказательство. Пусть (p,x,7) - зацикливающая конфигурация автомата M. По определению зацикливающей конфигурации для любого i > 1 существует конфигурация (рг,х,7г), такая, что 7г > 7 и (p, x,y) =г (рг,х,7г). Из детерминированности автомата M следуют соотношения

(р, х, 7) = (р1, х,= (р2, х, 72) = . . .

Рассмотрим начало данной последовательности, имеющее \V(M) + 1 членов. Ему отвечает маршрут с пустой пометкой, среди вершин которого есть хотя бы две одинаковые. Следовательно, маршрут этот содержит цикл, который, как и весь маршрут, имеет пустую пометку. Из неравенств > , где i любое, следует, что это нейтральный или накапливающий цикл. Отсюда выводим, что C+(M) = 0.

Пусть теперь C+(M) = 0. Тогда существует предложение T, которое содержит нейтральный или накапливающий цикл с пустой пометкой. Представим T в виде