Пусть m > 1, а = yixi... ym-ixm-iym - структура. Пусть Step = {ujZjVj 1 <

j < m, Uj yj Vj = a, Zj G DelPair(yj )}U{ui Ziwij Zj Vj 1 < i < j < m, uiyiwij yj Vj = а, ZiWijZj G PrDel(yi,wij,yj)}. Тогда если Step = {а}, то reduction(yi, xi, ... ,ym-i, Xm-i,ym) = {а}, иначе reduction(yi,xi,... ,ym-i,xm-i,ym) = UZlXl,„Zm lXm lZm£s4ep

reduction(Zi,xi, . . Zm-1, Xm-1, Zm).

"Редукция"приводит структуру а к виду

uixi . . . ит-1хт-1ит)

где никакая из цепочек и не содержит итераций и никакая пара (и,Uj) не содержит циклов одной и той же итерации.

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

Лемма 10. Если

yixi . . . ym-lxm-lym

то для любой

а G reduction(yi,xi,... ,ym-i,xm-i,ym) верно соотношение а G SG □

Определим на множестве структур следующие бинарные отношения.

(а, а) gTg 3(p, x, y, Z, и, v) : [а = u(pZ)pV, а = u(px(pZ)py)pV,

(px(pZ)py)p определяет элементарную ритерацию (x,Z,y)]. Будем говорить, что а является развитием структуры а с историей (развития)

(px, (pZ)p,y)p,v).

Назовем отношение fg=TG отношением развития. Если последовательность а0,...,ат такова,что для 1 < i < m является развитием структуры а-1 с некоторой историей hi = (ui,xi,Zi,yi,Vi), то будем говорить, что последовательность (hi,..., hm) реализует соотношение а0 fG ат.

Индекс G, как обычно, опускаем всегда, когда для этого есть возможность.

Лемма 11. Пусть а G SG - Canons(G). Тогда некоторая подцепочка цепочки а определяет элементарную итерацию.

Доказательство. Из определения канона следует, что а содержит цепочку, определяющую итерацию. Выберем среди таких цепочек наименьшую по длине. Предположим, что выбранная цепочка W определяет неэлементарную p итерацию. То гда w = (px(pZ)py)p для некоторых x,y,Z и некоторая подцепочка цепочки x(pZ)py определяет итерацию и имеет меньшую длину, чем W. Но это противоречит вы бору цепочки w □

Лемма 12. Пусть а G SG, (а0,а) G с историей (u, (px, (pZ)p,y)p,V). Тогда суще -ствуют такие структуры u, V, что u{px{pZ)py)pV G Canons(G).

Доказательство. Рассмотрим структуру

а = u(px(pZ)py)pV G reduction(u, (px(pZ)py)p, v).

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

W1 = {qx1 {qx5{qz1) qy5)q y1 )q,

определяющую сложную итерацию.

Согласно определениям элементарной итерации и развития цепочка x{pz)py не может содержать в себе цепочки, определяющей итерацию. Следовательно, w1 либо содержится целиком в u или v, либо какаялибо из цепочек {qz1)q, x5{qz1)qy5, Xj, yi, i = 1,2, 3,4, 5, содержит в себе цепочку {px{pz)py)p. В первом случае цепочка, содержащая в себе w1, может быть уменьшена операцией DelPair. Во втором случае u или v (или они обе) могут быть уменьшены операцией DelPair (или, соответственно, операцией PrDel(u, {px{pz)py)p, v) ). Каждый из рассмотренных случаев противоречит "неуменьшаемости"цепочек u, v, следующей из определе ния операции reduction. Следовательно, о является каноном. Так как о Е SG, из леммы 10 следует, что о Е Canons(G) □

Теорема 4. Для каждой структуры о Е SG существует такая о Е Canons(G), что (о, о) Eff и для любого элемента (u,x, z,y,v) последовательности, реализующей последнее соотношение, xzy входит в некоторый канон из Canons(G).

Доказательство. Достаточно рассмотреть структуру о, имеющую сложную итерацию. По лемме 11 о содержит цепочку, определяющую элементарную итерацию. Пусть

о = u{px{pz)py)pv, где {px{pz)py)p определяет элементарную ритерацию (x,z,y). Пусть

оо = о, о1 = u{pz)pv

Тогда (о1,о0) Е с историей

hi = (гц,x1,z1,y1,v1) = {px, {pz)p,y)p,v)

По лемме 12 x1z1y1 входит в некоторый канон из Canons(G).

Если о1 имеет сложную итерацию, то аналогичным образом строим такую структуру о2, что

(о2, о1) Е с историей h-2 = (U2, x2, z2, y2, v2),

в которой x2z2y2 - подцепочка некоторого канона из Canons(G), и т.д. Так как < для i > 1, процесс закончится для некоторого k > 1 построением структуры ок, не имеющей итераций, и такой, что (ок,о) Ек. При этом в по -следовательности (hk, , h1), реализующей соотношение (ок, о) Е, для каждого hi = (ui,xi, zi,yi,vi), 1 < i < k, xiziy; входит в некоторый канон из Canons(G). Вследствие леммы 10 о; Е SG, 1 < i < k. Следовательно, ок Е Canons(G) □

Пусть структура о такова, что со(о) Е (£U{±})*. Тогда назовем о терминальной структурой.

Назовем ядром грамматики G множество

Core(G) = {о Е Canons(G) о - терминальная структура}-

Из доказательств теоремы 4 и леммы 12 следует

Теорема 5. Для каждой терминальной структуры о Е SG существует такая о Е Core(G), что (о, о) Е f и для любого элемента (u, x, z, y, v) последовательности,

реализующей последнее соотношение, xzy входит в некоторый канон из Core(G) □

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

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

Самовставляющийся символ неизбежно порождает цепочки, определяющие итерации. Естественно по таким именно цепочкам проверять, имеет ли место самовставление (другими словами, участвует ли операция согласованной итера ции в бесконтекстном выражении, связанном с данным ядром). Учтем также, что если Ap - самовставляющийся символ, порождающий цепочку xApy, где x и y - непустые терминальные цепочки, то появление символов цепочек x и y может быть обусловлено разными правилами грамматики. Изза этого явление самовставления может обнаруживаться не по любой ритерации, а лишь по достаточно сложно устроенным. В самом деле, рассмотрим следующее утверждение и устройство обсуждаемых в нем терминальных структур.

Утверждение 3. Пусть а = uwv есть терминальная структура, в которой це -почка w определяет ритерацию (xiax2,z, yiby2), где a, b e E. Тогда существует терминальная структура а = uwv e Core(G), в которой цепочка w определяет ритерацию (x1ax2,z, yiby2).

Доказательство. Пусть

а e reduction(u, (p,xba,x2, (p, z, >p,yi,b,y2, )p,v). Тогда a представляется в виде a = uwv, где

w = (px ax2(pz>py by2>p

определяет ритерацию требуемого вида.

Предположим, что а не является каноном. Это означает, что некоторая подце -почка

S = (qS5 . . . (qs1(qr>qt1>q . . . t5>q

структуры a определяет сложную (/итерацию. Но при любом положении в а скобок (q, >q цепочки s получается, что в цепочке а, вопреки ее построению, еще можно удалить циклы какойлибо из пар (si,ti), 1 < i < 5, не затрагивая шести выделенных участков (p, a, (p, >p, b, >p. Итак, а является каноном и, вследствие леммы 10, входит в Core(G) □ Заметим, что цепочка вида

s = (qS4 . . . (qS (qГ>qt>q . . . t4>q,

определяющая простую итерацию, может присутствовать в а, если s4 содержит первую, а S - вторую из выделенных открывающих скобок (p, t4 и t содержат