Заметим, что "скобочное поведение"присуще в бесконтекстных языках объектам, которые, на первый взгляд, трудно назвать скобками.

Пример 2. Грамматика

S - Л аЛЪБ ЪБаБ A - Л аАЪА Б - Л ЪБаБ

порождает цепочки, в которых а и Ъ поровну. Она указывает, что минимальный из непустых префиксов такой цепочки, в свою очередь принадлежащих данному языку, является скобочной системой с парой скобок (а, Ъ) или (Ъ, а).

Пример 3. В цепочках, порождаемых грамматикой G с правилами

S - Л aSЪS, (а, Ъ) е {(begin, end), (вазе, end)},

моделируется поведение символов, ограничивающих составной оператор и опера тор варианта в языке ПАСКАЛЬ [Wirth 71]. Отметим, что L(G) не удовлетворяет определению языка Дика.

Пусть Е( и Е) - непересекающиеся алфавиты. Тогда назовем непустое множество

P С Е( х Е)

Вмиожеством , а язык LP, порождаемый грамматикой

S - Л aSЪS, (а, Ъ) е V,

Оязыком (над Вмиожеством P).

Язык Дика является Dязыком. Обратное неверно, как показывает пример 3.

Пусть А = Е( U Е), w е А*. Пусть отображение

ц : А* - А*

определяется равенством /j,(w) = t, где t есть результат применения к w следующих действий:

t := w;

пока для некоторых (а,Ъ) е P и w1,w2 е А* справедливо равенство t = ww2, выполнять присваивание t := w\w2.

Тогда назовем ц D-отображением.

Заметим, что D отображение стирает цепочки D языка, и

LP = {w е А* fi(w) = Л}.

Пусть цепочка y е А* такова, что для некоторых x и z из А* цепочка xyz е LP. Тогда назовем y фрагментом (скобочной системы xyz).

Пусть x е LP. Определим рекурсивно неотрицательное целое рагЫ(х) и назовем его протяжением цепочки x:

1)раШ(Л) = 0;

2)если y е LP, (а,Ъ) е P и x = ayЪ, то ратЫ) = 1;

3)если y,z е LP и x = yz, то parti(x) = parti(y) + parti(z).

Назовем шириной цепочки x е LP число width(x) = max{paтti(z) z е LP, x = uzy для некоторых фрагментов u и y}.

Назовем глубиной цепочки x G LP число depth(x), рекурсивно определяемое следующим образом:

1)depth(K) = 0;

2)если x,y G LP и (a,b) G P, то depth(axb) = depth(x) + 1, depth(xy) = max(depth(x), depth(y)).

Пример 4. Пусть P = {(a,b), (a, c)}, x = aabacaccac. Тогда x G LP, parti(x) = depth(x) = 2, width(x) = 3. Действительно, цепочка x является сцеплением двух непустых скобочных систем, в которых начальный и конечный символы парны друг другу: aabacacc и ac. Первая из этих систем имеет глубину 2, вторая - 1. Фрагмент abacac имеет протяжение 3.

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

Теорема 1. Пусть w,d - неотрицательные целые. Пусть цепочка ф G LP удовлетворяет неравенствам width() < w, depth() < d. Тогда ф < gW)d, где число gw,d определяется следующими рекуррентными соотношениями:

1)= 2w,

2)9w,d = (9w,d-i + 2)w, d> 1.

Доказательство. Пусть n = parti). Тогда цепочка ф представляется в виде ф = ф1... фп, где фг G LP - {Л} для i = 1,..., n. Заметим, что n < w. Очевидно,

ф = фг .

Докажем теорему индукцией по d. При d = 1 имеем фг = 2 для 1 < i < n. Следовательно,

ф = 2n < 2w = 9Wi1.

Пусть d > 1 . Предположим, что теорема верна для цепочек, глубина которых не превосходит d - 1, а ширина не превосходит w. Из выбора числа n следует, что цепочка фг, 1 < i < n, имеет вид ai£ibi для некоторых £г G LP, (ai, bi) G P, причем depth(i) < d - 1. Из определения ширины следует, что width (£) < width) для любого фрагмента £ G LP цепочки ф G LP. Следовательно, width(£i) < w, так как £г - фрагмент цепочки ф.

По предположению индукции £г < gW;d-1. Следовательно,

фг = £г + aibj < 9w,d-1 + 2,

ф < (gw,d-1 + 2)n < (gw,d-1 + 2)w =

□

1.2. Эграфы и магазинные автоматы

1.2.1. Определение Эграфа. Пусть для любого Dмножества PC Е( х Е) записи Left(P) и Right(P) обозначают соответственно множества

{a G E(3b G Е) (a,b) G P}

{b G E)3a G E( (a,b) GP}.

Назовем Ографом шестерку D = (Е, V, V, Л, P0, F), где: Е - алфавит пометок дуг;

V- конечное множество вершин; P0 Е V - входная вершина;

F С V - множество заключительных вершин;

V- Dмножество; объединение

E(D) = Left(V) U Right(V)

есть множество дуг; это ориентированные нагруженные дуги;

Л : E(D) - Vх (ЕU{A}) х V - функция положения (дуги в Dc); элементы тройки

(P, a, Q) Е V х (Е U {A}) х V,

которая удовлетворяет равенству (P, a, Q) = Л(п) для некоторой дуги п, интерпретируются соответственно как начальная вершина, пометка и конечная вершина этой дуги.

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

Пусть для любого пути T beg(T) и end(T) обозначают соответственно его на -чальную и конечную вершины. Пусть pair(T) обозначает упорядоченную пару

( beg( T), end( T)).

Понятие пометки пути в графе D определим рекурсивно: пометка пустого (или тривиального) пути пуста, а для пути Tn, в котором п Е E(D) и, следовательно, Л(п) = (P,a,Q) для некоторых P,Q Е V и a Е Е U {Л}, пометка есть u(Tn) = u(T )a.

Элемент множества путей

Sentences(D) = {T Е Lp\beg(T) = Po, end(T) Е F}

назовем предложением D графа D.

Будем говорить, что Dграф D определяет язык

L(D) = {u(T) \ T Е Sentences(D)}.

Условимся опускать разделители в записи тройки Л(п), если это не мешает различить ее элементы.

Пример 5. Рассмотрим

Di = ({a,b}, {P, Q}, {(1,2), (1,3)}, Лъ P, {Q}),

где Л1(1) = PaP, Л1(2) = PbQ, Л1(3) = QbQ.

Множество всех его путей из входной вершины P в заключительную вершину Q можно описать формулой

{1k23l\k,l > 0}. Sentences(Di) = {1n23n-1 \n > 1}. L(Di) = {anbn\n > 1}. Теперь наша цель - доказать следующую теорему.