Теорема 2. Язык тогда и только тогда является бесконтекстным, когда он определяется некоторым Dграфом □

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

1.2.2. Преобразование магазинного автомата в Drpacp

Магазинный автомат есть семерка M = (K, Е, Г, Z0, 5, p0, F), где:

K - конечное множество состояний;

Е - входной алфавит;

Г - магазинный алфавит;

Z0 е Г - маркер дна магазина;

p0 е K - начальное состояние;

F С K - множество заключительных состояний;

5 С K х (Е U {Л}) х Г х K х Г* - конечное множество команд.

Это определение отличается от приведенного в [Ginsburg 66] только интер-претацией элемента 5. Понятие команды удобно для сопоставления магазинных автоматов с D графами.

Язык L(M), допускаемый автоматом M, определяется с помощью понятия кон -фигурации и бинарного отношения достижимости, заданного на множестве кон -фигураций.

Далее, если не оговорено иное, считаем, что

p,q е K, а е Е и{Л}, x,z е Г, y е Г*.

Правый символ магазинной цепочки отвечает верху магазина. Команду обознача -ем записью

(p, а, Z) (q,7).

(p, ax, YiZ), (q, x, yiy) е K х Е* х Г*, в = (p, а, Z) - (q, 7) е 5.

Тогда пара

((p, ax,7iZ), (q,x,7i7)) в

принадлежит бинарному отношению =. Определим отношение =M как объеди -

нение ив65 =. Пусть p е K, x,y е Е*, 7 е Г* и

((p0,x,Z0), (p,y,7)) е =M .

Тогда назовем тройку (p, y, 7) конфигурацией магазинного автомата M. Конфигу -рацию (p0,x,Z0) назовем начальной, конфигурацию (p, Л, 7), где p е F, - заключительной.

Теперь язык L(M) можно определить формулой

L(M) = {x е Е*3(p е F, 7 е Г*) (p0, x, Z0) =M (p, Л, 7)}.

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

Пусть в = (p, a, Z) - (q, 7) G 5, 7 = Wi... Wn, n > 0, W G Г для 1 < i < n, +, - G Г. Назовем следом команды в цепочку а (в), где а (в) = -Z + Wi... + Wn при n > 1 и Z = Wi, а (в) = +W2... + Wn при n > 1 и Z = Wi, а(в) = Л при 7 = Z, а(в) = -Z при 7 = Л. Здесь минус символизирует удаление из магазина символа Z, плюс - запись в магазин символа цепочки 7.

Пусть магазинный автомат M = (K, Е, Г, Z0, 5, p0, F) удовлетворяет следующим условиям:

1)след любой команды есть +X или -X для некоторого X G Г;

2)любая конфигурация имеет вид (p, x,Z07), где 7 G (Г - {Z0})*, p G K, x G Е*;

3)заключительная конфигурация имеет вид (f, Л, Z0), где f G F. Тогда назовем автомат M совершенным.

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

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

Доказательство. Лемма верна, так как следующий алгоритм 1 строит по любому магазинному автомату M эквивалентный совершенный магазинный автомат M. Алгоритм вводит дополнительные состояния, магазинные символы и команды, чтобы избавиться от команд, выполняющих с магазином операцию, недозволен ную в случае совершенного автомата □

Команду в назовем нейтральной, если а(в) = Л, накапливающей, если а(в) = +X для некоторого X G Г, и стирающей, если а(в) = -Z.

Алгоритм 1. Совершенствование магазинного автомата.

Вход. Магазинный автомат M = (KЕ, Г, Z0, 5,p0, F).

Выход. Магазинный автомат M = (K, Е, Г, Z0, 5,p0, F).

Шаг 1. (Обеспечивает вид Z07, где 7 G (Г - {Z0})*, третьего элемента конфигурации.)

Г:=Г U{Z0}, Z0 G Г;

5 := 5 U{(p0, Л) - (P0,Z0Z0)}.

Шаг 2. (Обеспечивает равенство 7 = Z0 для третьего элемента 7 заключитель ной конфигурации.)

K := K U{fi,f}, где fi,f G K;

5 := 5 U{(p, ) - (fi,Z) p G FZ G Г}и

{(fi, ) - (fi, Л) Z G Г}и

{(fi, Л) - (f,Z0)};

F := {f}.

Шаг 3. (Преобразует команды так, что каждая команда результирующего автомата является либо накапливающей, либо стирающей.)

K := K U {p, G K в = (p, a, Z) - (q, Wi ... Wn), Z = Wi, n > 1}.

Каждую команду вида

в = {p,a,Z) - (q,Wi ...Wn),

где Z = Wi и n > 1, заменить командами

(p, a, Z) - (pe, Л), (pe, Л, X) - (q, XWi... W„), X e Г.

K : = K U {рв}, e K в = (p, a, Wi) - (q, Wi ... Wn), n > 2, 2 < i < n - 1}. Каждую команду вида

в = (p,a,Wi) - (q,Wb..W„),

где n > 2, заменить командами

(p, a,Wi) - (p0;2,WiW2),

(po,i, Л, Wi) - (pe)i+i, WiWi+i), 2 < i < n - 2,

(pe,n-i, Л, W„ i) - (q, W„ i Wra). Г := Г U {Ze e Г команда в e 8 является нейтральной}.

Заменить любую нейтральную команду

в = (p, a, Z) - (q, Z)

двумя командами

(p, a, Z) - (p, ZZe), (p, Л, Ze) - (q, Л).

Далее считаем магазинный автомат

M = (K, Е, Г,Zo,8,po,F)

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

Пусть y = Xi... Xn, где n > 0 и X» e Г для 0 < i < n. Тогда будем обозначать цепочку +Xi... + Xn записью +7, а цепочку -Xn... - Xi записью -7.

Пусть (p, x, yy) - конфигурация, 171 > 1. Тогда назовем пару (p, +7) памятью. Заметим, что при

Е( = {+X X e Г}

Е) = {-X X e Г}

множество А = Е( U Е) можно интерпретировать как алфавит языка Дика. Следовательно, законно применение Dотображения к цепочкам из А*.

Пусть р - память. Рекурсивно определим вычисление T (над памятью р), его пометку ш(Т), след a(T), конечную память ecol(T) и длину T:

1)пара T = (р, Л) с пустым вторым элементом есть (пустое) вычисление; co(T) = a(T) = Л, ecol(T) = р, T = 0;

2)пусть Ti = (р, О) - вычисление и ecol(Ti) = (p, z + Z), где Z e Г, z e А*; пусть в = (p, a, Z) - (q, 7) - такая команда, что

w = (z + Za(e)) e Е+.

Тогда пара T = (р, Ов) есть вычисление, причем o>(T) = w(Ti)a, a(T) = a(Ti)a(e), ecol(T) = (q, w), T = Ti +1.