Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[8]

Выход. Магазинный автомат M(D), определяемый шагом 3 алгоритма. Шаг 1. PPDA := 0; VPDA := {[P0, Z0]}.

Шаг 2. Пока множество VPDA пополняется новыми вершинами, выполнять следующие два действия:

1)положить новое значение множества PPDA равным объединению PPDA и множества

{([P, Z]w(ni)[end(ni),ni], [Ьед(п2),П1]и(п2)[еп(1(п2, Z])

[P, Z] G VPDA; (ni, П2) G P; бед(тп) = P};

2)добавить в VPDA вершины дуг, образующих пары из PPDA.

Шаг 3. Положить M(D) равным семерке (Vи{/}, X, Left(P)U{Z0}, Z0, {(p1,a1, Z) (qi,ZX), (P2,a2,X) (q2, Л) ([pi,Z]ai[qi ,X], [p2, X]a2[q2, Z ]) G PPDA}U {(P, Л,Zo) (f,Zo)P G F},Po, {/}).

Положить APDA(PaQ) равным (P, a, Q) для P, Q G VPDA, a G X и{Л}, PaQ G Le/t(PPDA) U Right(PPDA).

Термин "маршрут", введенный при построении графа магазинного автомата, будем применять и в случае произвольного Dграфа (X, V, P, A, P0, F), т.е. будем использовать слово "маршрут"как сокращение оборота "путь, который являет ся фрагментом некоторой цепочки Dязыка LP". Будем называть нейтральным маршрут, который является цепочкой Dязыка LP. Это уменьшит насыщенность текста формулами. Слово "нейтральный"напоминает о "заряженности"маршрутов магазинного автомата. Нейтральный маршрут магазинного автомата имеет пустой заряд и является основой вычислений, которые не стирают никакую часть исходного содержимого магазина, но обязательно стирают собственные записи в магазине, т.е., в конце концов, ничего к нему не добавляют.

Нетрудно заметить, что маршруты графа G(D) отличаются от маршрутов графа D только тем, что каждая их вершина содержит дополнительно некоторый символ магазинного алфавита автомата M(D). Символ, отвечающий конечной вершине маршрута T графа D, где beg(T) = P0, можно охарактеризовать следующим об -разом: если T нейтрален, это Z0, иначе это последняя из его дуг, для которых T не содержит парной дуги.

Утверждение 1. L(M(D)) = L(G(D)) = L(D).

Доказательство. Естественно считать, что запись TiPT2, где

end(Ti) = P = beg(T2),

обозначает тот же путь, что и запись TiT2. Используем это соглашение уже в определении следующей функции, помогающей описать соответствие предложе ний графов D и G(D).

Функция Ф(Т, Z), где T - нейтральный маршрут графа D, Z G {Z0}ULe/t(P), определяется следующими рекуррентными соотношениями:

1)если маршрут T пуст, то

Ф(Т, Z) = [P,Z],

где P - вершина маршрута T;

2)если T = niTin2T2, где Ti и T2 нейтральны, (ni,n2) G P, то

Ф(Т, Z) = i*(Ti,ni)2*(T2,Z),


ipi = [beg(ni),Z]u(ni)[end(ni),ni],

Ф2 = [beg(n2),ni]w(n2)[end(n2), Z]. Сопоставляя данное определение с алгоритмом 2, видим, что значение функции имеет форму маршрута графа G(D), но, возможно, таковым не является, так как пары

[beg(ni),Z ], [end(n2),Z ] не обязаны входить в VPDA, а образование

([beg(ni), Z]u(ni)[end(ni),ni], [beg(n2),ni]u(n2)[end(n2), Z])

не обязано входить в PPDA.

Пусть ExtP обозначает следующее расширение множества PPDA:

ExtP = {([pi, Z]aiQi,Q2a2[p2, Z])\3X E {Zo} U Left(P) ([pi,X]aiQi,Q2a2[p2,X]) EPPDA}. Тогда ясно, что значение функции однозначно определяет некоторую цепочку x Dязыка CExtp, который содержит в себе Dязык LPPDA и, следовательно, его подмножество Sentences(G(D)). Существенно, что цепочка x либо является нейтральным маршрутом графа G(D)), либо отличается от такового лишь магазинным символом в конечных вершинах его нейтральных начальных участков.

Легко доказать индукцией по k > 0, что началу цепочки 4t(T, Z), которое имеет длину 2k и принадлежит Dязыку LExtP, отвечает конечная "вершина"

[end(T), Z] E V х ({Zo} U Left(P)). Учитывая конструкцию Dграфа G(D)), получаем отсюда равенство

Sentences(G(D)) = {4>(T, Z0)\T E Sentences(D)}.

Значит, L(G(D)) = L(D). Следующее равенство вытекает из построения автомата M(D): Sentences(Graph(M(D))) = {TiT2\Ti E Sentences(G(D)); T2 отвечает ко -манде с пустым следом, переводящей автомат M(D) в заключительное состояние f; luT) = Л}. Следовательно, L(M(D)) = L(D) □

Пример 7. Построим с помощью алгоритма 2 магазинный автомат M(Di), эк -вивалентный Dграфу Di, определенному в примере 5. Выпишем его команды в порядке построения определяющих их дуг графа G(Di):

(P,a,Zo) (P,Zo PaP),

(P, b, PaP) (Q, Л),

(Q, b, PaP) (Q, Л),

(P, a, PaP) (P, PaP PaP),

(Q, A,Zo) - (f,Zo).

Данный пример показывает необходимость особого заключительного состояния f E V (см. алгоритм 2) и команд вида

(Q, A,Zo) - (f,Zo),

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


Заметим, что в статьях и монографиях, в которых строится пример магазинного автомата для языка {anbnn > 1}, используется именно такой принцип организации автомата, какой наблюдается в случае автомата M(Di). Автомат является детерминированным и работает в реальном времени, пока цепочка языка не прочитана. Первая половина входной цепочки целиком поступает в магазин в той или иной кодировке.

1.3. Ядро Эграфа

1.3.1. Определение ядра. В определении ядра Dграфа большую роль играет следующее понятие цикла, несколько суженное по сравнению с употребляемым в теории графов.

Пусть T - непустой маршрут и beg(T) = end(T). Тогда назовем маршрут T циклом.

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

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

Пусть T - нейтральный маршрут Dграфа D, w и d - положительные целые. Пусть T удовлетворяет следующим условиям: если Ti,... , Tm - такие нейтраль -ные циклы, что цикл Ti... Tm является участком маршрута T, то m < w; если Tii,..., Tim, T21, T31, ..., T3m таковы, что T2(i+i) = TuT2iT3i, 1 < i < m, есть гнез -до маршрута T, образованное циклами Tii и T3i, то m < d. Тогда назовем T (w,d)-каноном Dграфа D.

Множество (w, d)канонов графа D назовем (w, d)-ядром графа и обозначим через Core(D,w,d). Ради краткости пишем далее "канон", "ядро"и " C or e(D)"вместо "(w, d)канон", " )ядро"и " Core(D, w, d)"соответственно.

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

Утверждение 2. Пусть k, m и n - натуральные числа и

k > (n - 1)m.

Кортеж k натуральных чисел, не превосходящих m, содержит не менее n одина -ковых чисел.

Доказательство. Пусть число 1 < i < m входит в рассматриваемую последова -тельность ki > 0 раз. Тогда длина последовательности есть m=i h. Предположим, что для любого целого 1 < i < m верно неравенство kj < n. Тогда

ki < (n - 1)m < nm.

Однако длина последовательности равна nm □

Лемма 3. Пусть m есть число вершин Dграфа D. Ширина и глубина канона графа D ограничены числами (w + 1)m и (d + 1)m2 соответственно.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]