грамматику, определяемую правилами

{Ap - (pXpi... Xpnp}p 0 < p < s; {p, )p - новые символы}. О выводе

Xi ==g . . . ==g Xm, m > 1,

будем говорить, что он реализует соотношение

Напомним, что правый вывод, реализующий соотношение A ==G x, может быть представлен последовательностью правил или их номеров.

Ясно, что между правилами грамматик Augm(G) и Struct(G) существует взаимнооднозначное соответствие. Будем считать, что соответствующие правила имеют в своих грамматиках один и тот же номер. Используем это обстоятельство в следующем определении.

Пусть A Е N U {So}, пусть соотношения

A ==Augm(G) X

A =Struct(G) °

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

Если а - структура цепочки x, то будем писать а Е struct(x), x = и (а).

Обозначим через br(a) (от braces) результат вычеркивания из а символов цепочки и (а). Заметим, что Ьг(а) является скобочной системой над Dмножеством

{({p, )p) 0 < p < s}.

Будем применять операцию br и к подцепочкам структур.

О подцепочке z некоторой структуры будем говорить, что она сбалансирована, если br(z) - скобочная система.

Пусть 1 < p < s; пусть

а = u{px{pz)py)pv

есть структура, в которой z и w = {px{pz)py)p сбалансированы. Тогда будем говорить, что цепочка w определяет p-итерацию (x, z, y) с циклами x и y. При этом pитерацию будем называть элементарной, если для любого 1 < q < s никакая подцепочка цепочки x{pz)py не определяет qитераций.

Термин p итерация отражает повторение в выводе применений p го правила. Приставку p будем опускать, когда правило несущественно.

Пусть для 1 < i < 5 подцепочка

{pzi)p {pxi . . . {px5{pz6)py5)p . . . yi)p

цепочки

w = {pxi . . . {px5{pz6)py5)p ...yi)p

определяет pитерацию (xi,zi+i,yi). Тогда назовем любую из pитераций, определяемых цепочкой w, сложной. Итерацию, которая не является сложной, назовем простой.

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

Множество сентенциальных форм грамматики Struct(G) обозначим через SG. Введем обозначение Canons(G) = {а Е SG а является каноном}.

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

Пусть l - положительное целое, selection(LP, l) = {ф Е LPV(a, b) Е V max{nl 3{xi, yi Е Lp I1 < i < n,axiyib,axi ...xnyn ...yib Е Lp} : ф = axi... axnynb... yib} < l}.

Утверждение 2. Если ф Е selection(LPто depth(p) < lV.

Доказательство. Пусть n = depth), m = V. Не ограничивая общности, можно полагать, что ф имеет вид ai... anbn .. .bi, где (ai, bi) Е V для 1 < i < n.

Докажем утверждение индукцией по m. В случае m =1 из определения множества selection(LP,l) следует, что n < l = lm. Пусть k > 1. Предположим, что утверждение верно для 1 < m < k, и рассмотрим случай m = k. Обозначим через £ цепочку Dязыка над Dмножеством V - {(ai,bi)}, получаемую из ф вычеркиванием всех вхождений парных символов ai, bi. Согласно определению множества selection(LP,l) имеем depth(£) > n - l. По предположению индукции depth(£) < l(m - 1). Следовательно, n - l < l(m - 1), т. е. n < lm □

Заметим, что в случае языка Дика мощность Dмножества совпадает с числом открывающих скобок (или, что то же, с числом закрывающих скобок).

Пусть r - максимальная из длин правых частей правил грамматики G, т.е.

r = max{np 0 < p < s}. Из построения грамматики Struct(G) следуют

Лемма 6. Подцепочка y Е (V U {})* структуры удовлетворяет неравенству

y r □

Лемма 7. Для z Е V* соотношение x(pz)py Е SG верно тогда и только тогда, когда Ap -> z Е P и xApy Е SG □

Глубину и ширину скобочной системы br(a) будем кратко называть глубиной и шириной структуры а.

Лемма 8. Глубина канона не превосходит 5(s + 1). Доказательство. Справедливо соотношение

(а)а Е Canons(G)} С selection(L{pt)p\0<p<s}, 5),

так как канон не содержит сложных итераций. Но тогда лемма следует из утвер ждения 2 □

Лемма 9. Ширина канона не превосходит r.

Доказательство. Пусть структура а является каноном. Предположим, что ее ширина w больше r. Тогда а представляется в виде

а = u(poxi(piyi)pi . . . xw{pwyw)pwx0)povi

где br(xi) = Л (т. е. x не содержит угловых скобок) для 0 < i < w и цепочка yj сбалансирована для 1 < j < w. Но, по лемме 7, цепочка

также является структурой, и

xlApi xw Apw x0

есть правая часть правила р0. Но такое правило противоречит определению числа r, так как

I x1Ap1 xw Apw x0 w > r

□

Теорема 3. Если a e Canons(G), то

a < (r + 1)gr,5(s+1) - r.

Следовательно, множество Canons(G) конечно.

Доказательство. Из лемм 8, 9 и теоремы 1.1 об оценке сверху длины скобочной системы с ограниченными глубиной и шириной следует, что число угловых скобок в структуреканоне не превосходит числа gr>5(s+1). Так как первый и последний символы в структуре из Canons(G) являются скобками (0 и )0 соответственно, она содержит не более gr,5(s+1) - 1 подцепочек вида b1xb2, где b1 и b2 - скобки, а x не содержит скобок. Теперь из леммы 6 следует, что структураканон содержит не больше r(gr>5(s+1) - 1) символов из V U{±}. Откуда и следует теорема □

2.1.3. Определение ядра. Теорема о развитии для бесконтекстных грамматик. Далее удобно называть структурой и любую часть цепочки из SG.

Следующая функция отображает структуру во множество структур. Если a не имеет итераций, то

DelPair(a) = {a},

DelPair(a) = {u(pZ)pV 3(x, y) : a = u(px(pZ)py)pV и {px{pz)py)p определяет pитерацию (x,z,y)}.

Можно сказать, что операция DelPair вычеркивает циклы некоторой итерации. Так как структура может иметь не одну итерацию, такими вычеркиваниями можно получить множество структур, содержащее больше одного элемента.

Следующая функция отображает разбиение структуры во множество структур. Пусть xyz - структура; тогда если циклы некоторой итерации "расположены"один в x, другой в z, то

PrDel(x,y,z) = {x1(px2yz2)pz1 1 < p < s,

3(u,v) : (x = x1(pu(px2, z = z2)pV)pz1, (u,x2yz2,v) - ритерация )},

PrDel(x, y, z) = {xyz}.

PrDel отличается от DelPair тем, что "не затрагивает"вычеркиваниями выде ленный участок y заданной структуры xyz.