Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 70

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 64 65 66 67 68 69 < 70 > 71 72 73 74 75 76 .. 136 >> Следующая

• ос
7 А. В. Гладкий
194 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
л
Рис. 13.
И Ф, Т, 0 — метки при а, р, у соответственно, то Т© непосредственно сокращается до Ф; в этом сокращении Т является «аргументом», а 0 — «оператором» (поскольку метки при узлах Т' не содержат символа /), так что 0 = [Т\Ф], и Т — элементарная категория («знаменатели» всех категорий, входящих в значения элементарны). Таким образом, все левые узлы Т' помечены элементарными категориями, а все правые — неэлементарными.
Рассмотрим невисячий узел а дерева V такой, что а) а — правый узел или совпадает с корнем Т’\ б) в полном а-поддереве %' дерева Т все правые узлы, отличные от а, висячие; такой узел обязательно существует (аналогично предыдущему). Пусть pt,
Рг....Рь — все отличные от а левые
узлы г', упорядоченные сверху вниз, и а = ао, ось • • •, «ft — все остальные узлы х', упорядоченные так же (рис. 13). Обозначим через Ч**, 0j метки при аи Pj соответственно и через В, Ah, ..., At — те символы из V\, вхождениям которых в X соответствуют вхождения 0ft, Tft, ..., Yi в ц(Т'), отвечающие узлам р*, ан, ???, c*i дерева Т' (в этом порядке). Тогда X представляется в виде X = Y\BAu... A\Y2. Категории Wu ..., Yft, 0ft принадлежат f'(Ai), ..., f'(Ah), f'(B) соответственно. По предыдущему, категории 0i, ..., 0л элементарны, a Ч^, ..., Ч’ь неэлементарны; категория То либо неэлементарна, либо равна Ф0; кроме того, ^1=[в,\Т0] и V, == [еде*-!] при За-
метим, что Yi — правая Л i-категория, так как «числитель» неэлементарной левой категории всегда является элементарной категорией, отличной от Ф0.
Обозначим теперь через I наибольшее из чисел i, ... ..., k, для которого Ч^ есть правая Лгкатегория, и через т" —полное Р/_1 -поддерево Т' (если 1—1, считаем Рг—1 = а). Положим Т[ — Sub(Т', г", Рг-i). «Числитель» правой категории — левая категория; поэтому найдется такое D е №, что вг_1 является левой D-категорией. Если положить Х\ = YxDAi-\.. , A\Y2, (при /==1 пола-
S 6.U
КАТЕГОРИАЛЬНЫЕ ГРАММАТИКИ
195
гаем Х\= YiDY2), то ц{Т\) будет цепочкой категорий, сопоставляемой цепочке Хх функцией f. Отсюда, по индуктивному предположению, следует, что Хх выводима из / в Г. Поэтому для завершения доказательства достаточно установить, что цепочка BAuAk-i. ? ? Ai выводима в Г из D.
Поскольку 0* — элементарная S-категория, а
'Pfe-j....Ч^+1 — неэлементарные левые Ак~, Ак-Х-, ...
..., Лг+1-категории, они имеют соответственно вид Ср
[в!‘т'\фт>], .... К<Г\С?|«], где С, F, в],
С{, Fi^W. Но из равенства Yfc = [0&\0ft_,] получаем CF = BFkk. Далее из того же равенства вместе с равенством =[0fe_,\0fe_2] следует СРкк *= В^‘ и т.д. Имеем, таким образом: &к=в1, Ч'-* ={в?\в?_]], х1гк-} =
= [S*_i\fl*-21, • • •, Tt+i =[sf+i\Cf+i]. Отсюда, поскольку 0fe — В-категория и Ч^ — Лгкатегория, вытекает наличие в R правил F -*ВВк, Вк~* АкВк-и Bk-X -> Л*_,В6_2> ... ..., ВШ->АШСШ, что дает F \-BAkAk-, ... АШСШ.
Г
В то же время Т/= [0Д0/-1] = [cf+i\0/_i], и Ч*1/— правая Аг-категория, a @i-t — левая D-категория; но это в силу определения правой Лркатегории дает Сг+1 = Ai и F — D.
Итак, D |—ВАкАк-х ... Л/. Доказательство закончено, г
Подведем итог. Будем называть сложностью категории общее число вхождений в нее символов \ и / и сложностью К-грамматики — максимальную сложность категорий, входящих в значения ее приписывающей функции. Кроме того, назовем К-грамматику левосторонней (правосторонней), если категории, входящие в значения ее приписывающей функции, не содержат вхождений символа / (соответственно \ ). В последнем рассуждении мы имели дело с левосторонней грамматикой сложности, не превосходящей 2; ничто не помешало бы нам, разумеется, повторить это рассуждение для правосторонней грамматики. Суммируя, получаем следующую теорему.
Теорема 6.1. а) Для всякой К-грамматики можно построить эквивалентную ей Ъ-грамматику. б) Для вся*
7*
1Э6 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
кой Ъ-грамматики можно построить эквивалентную ей левостороннюю (правостороннюю) К-грамматику сложности, не превосходящей 2.
Следствие. Для всякой К-грамматики можно построить эквивалетную ей левостороннюю (правостороннюю) К-грамматику сложности, не превосходящей 2.
Замечания. 1. В теореме 6.1,6) нельзя заменить двойку единицей (упражнение 6.4); это невозможно и при отказе от односторонности (упражнение 6.5).
2. Назовем путь ао, аь ..., а8 в бинарном дереве л е-вым (правым), если узлы ai, ..., as левые (правые). Если ao, ai, .... as— правый путь в дереве сокращения левосторонней К-грамматики и узел ао помечен категорией То, то метка при а4 будет иметь вид pFi^o], метка при аг — вид plMf'Fi \Ч/о1] и т. д. Поэтому длина правого пути в дереве сокращения левосторонней К-грамматики не может превосходить сложности этой грамматики; аналогично для левых путей в деревьях сокращения правосторонних грамматик. Отсюда по теореме 6.1 получаем, переходя к канонически соответствующей Б-грамматике, что для всякой Б-грамматики Г можно построить эквивалентную ей стандартную бинарную Б-грамматику Г' такую, что длины правых (левых) путей в деревьях полных выводов в Г7 не превосходят 2.
Предыдущая << 1 .. 64 65 66 67 68 69 < 70 > 71 72 73 74 75 76 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed