Назовем память bcol(T) = р начальной памятью вычисления T. Назовем зарядом вычисления T цепочку /х(Т) = /i(a(T)).

Пусть p е K, W е Г, yi, 72 е Г*, р = (p, +W71) - память, T = (р, 0) - вычисление над памятью р, /(T) = - y1 + y2. Тогда назовем T маршрутом (над памятью р); если T = 1, то будем также называть T дугой.

Заметим, что если маршрут T пуст, то

ecol(T) = р = (p, +W).

Если T не пуст и последним элементом в последовательности 0 его команд является команда, переводящая автомат в состояние q, то

ecol(T) = (q, +W72).

Пусть p, q е K, w е A*, W е Г, y1, y2 е Г*, 0 е 8* таковы, что

T =((p,w + W71), 0)

является вычислением и /(T) = -y1 + y2. Тогда назовем основой вычисления T маршрут

(T) = ((p, +W71), 0).

Определим на множестве вычислений отношение ~м (~, если автомат подразумевается) следующим образом:

(T1,T2)e(T ) = в№).

Введенное отношение является отношением эквивалентности; эквивалентные вычисления имеют одну и ту же основу. В дальнейших рассмотрениях будут участвовать только маршруты, представляющие классы эквивалентности, на ко торые множество вычислений разбивается отношением ~. Это оправдано тем соображением, что внутренние свойства вычисления T не зависят от фрагмента, "отсекаемого"для получения основы в(T) этого вычисления.

Пусть (p, +Z) - начальная память некоторого пустого маршрута. Тогда пару (p, Z) назовем вершиной автомата (и упомянутого маршрута). Если p - заключительное состояние, то назовем вершину (p, Z) заключительной. Пару (po,Z0) назовем входной вершиной.

Отметим, что в случае совершенного магазинного автомата второй элемент заключительной вершины всегда есть Z0.

Лемма 2. 1. Пустой маршрут может быть представлен своей вершиной. 2. Непустой маршрут (р, 6 ... 6m), где m > 1 и 6 е 8 для 1 < i < m, может быть пред -ставлен последовательностью п1... nm дуг, вычисляемых следующим образом:

П1 = в((р, 61)),

П = в ((есо1((р, 61 ...6г 1)),6г))

для i = 2,..., m.

Доказательство. Часть 1 леммы следует из определений пустого вычисления, маршрута и вершины. Часть 2 нетрудно доказать индукцией по числу m команд во втором из элементов маршрута □

Пусть маршрут

ТГТ1ГТ1 ГТ1 ГТ1ГТ1

= Tonili±2Т3П3Т4

таков, что ni и п3 являются дугами и

MT2) = MTTi?2 T3) = (niTiT2T3n3) = Л. Тогда назовем тройку

(niTi, T2, Т3П3)

гнездом (маршрута T). Иногда будем называть гнездом и маршрут niTiT2T3n3. Будем говорить, что участки niTi, Т3п3 парны (друг другу), или образуют гнездо в маршруте T.

Пусть маршрут T таков, что bcol(T) = (p0, +Z0), ecol(T) = (f, +Z0) для f e F. Тогда назовем T успешным маршрутом (или предложением). Из определений следует, что совокупность пометок успешных маршрутов совершенного магазинного автомата есть язык, допускаемый автоматом.

Пусть V(M) есть множество всех вершин, определяемых пустыми участками успешных маршрутов автомата M, P(M) - множество всех пар дуг (ni5n2), таких, что ni и п2 парны в некотором успешном маршруте автомата M. Тогда ясно, что Dc})

Graph(M) = (Z, V(M), P(M), A(M), (po,Zo), {(p, Zo)\p e F}),

где функция положения A(M) сопоставляет дуге

п e Left(P(M)) U Right(P(M))

тройку (beg(n),u)(n),end(n)), эквивалентен автомату M.Graph(M) будем

называть графом магазинного автомата M. P(M) будем называть Dмножеством автомата M.

Конечность множеств V(M) и P(M) с очевидностью следует из конечности множеств K, X, Г и 8. Один из способов доказательства возможности постро -ения множеств V(M) и P(M) связан с понятием ядра, которое обсуждается в разделе 1.3. Эта возможность выводится из леммы 6 раздела 1.3. Таким образом, построение D графа по магазинному автомату завершено.

Пример 6. Пусть

M = ({p0,pi,p2,f}, {a,b}, {a,Z0},Z0,p0,8, {f}),

где множество 8 задается следующим перечнем команд:

(p0, a, Z) -> (p0, Za), Z e {Z{), a}, (p, b, a) - (pi, Л), p e {p0,pi},

(pi, Л, Z0) - (p2, Z0a),

(p2, Л, a) - (f, Л),

(f, b, Z0) - (p2, Z0a).

Тогда M есть детерминированный совершенный магазинный автомат. Он допус кает нерегулярный язык

{ambn\m > I, n > m}. Вершинами Dграфа Graph(M) являются пары

(p0, Z0), (p0, a), (pi, a), (pi, Z0), (p2, a), (f, Z0).

Здесь (p0, Zq) - входная вершина, (f, Zq) - заключительная.

P(Graph(M)) = P(M) = {(1, 5), (1, 6), (2, 3), (2,4), (7, 8), (9, 8)},

A(1) = (po, Zo)a(po, a), A(2) = (po,a)a(po ,a), A(3) = (po, a)b(pi,a), A(4) = (pi, a)b(pi,a), A(5) = (po, a)b(pi, Zo), A(6) = (pi, a)b(pi, Zo), A(7) = (pi, Zo)A(p2, a), A(8) = (p2,a)A(f,Zo), A(9) = (f,Zo)b(p2,a).

Дуги 3 и 5 отвечают стирающей команде

Их конечные вершины демонстрируют все те символы (и только те), которые бывают на верхушке магазина после выполнения данной команды. Аналогично, дуги 4 и 6 отвечают команде

(pi,b a) - (pb a). В то же время стирающей команде

(p2, A, a) - (f, A)

отвечает лишь одна дуга.

Множество успешных маршрутов автомата M задается формулой

{12k234k678(98)*fc, l > 0} U {1578(98)г/ > 0}.

Заметим, что путь (25) не является маршрутом. В самом деле, начальная и конечная памяти дуги 5 определяются однозначно:

bco/(5) = (po, +Zq + a), eco/(5) = (pi, +Zq).

А множество конечных памятей маршрутов, которые имеют начальную память (p0, +Z0) и заканчиваются дугой 2, есть

{(po, +Zo(+a)kk > 2}.

Оно не содержит памяти bco/(5).

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

Алгоритм 2. Построение магазинного автомата по Dграфу Вход.D = (S, V, P, A, Po, F).

Вспомогательные обозначения. Z0 G P; G(D) = (S, VPDA, PPDA, APDA, (Po, Zo), {(P, Zo)P G F}) - Dграф, множества VPDA, PPDA и функция APDA которого определяются шагами алгоритма; f G V.