Гладкий - Формальные грамматики и языки - 1973 (947381), страница 42
Текст из файла (страница 42)
2<2 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О В-ГРАММАТИКАХ <ГЛ 6 а 6.6> КАНонИНЕСКОЕ ПРЕдсТАВленИе в-языКА йз переменной 5<', (3) при 1 Ф 1 в !ю не должно быть пустого члена. Если перейти к грамматике, отвечающей системе (е), то порождаемый такой грамматикой язык и при сформулированных сейчас ограничениях может быть произвольным ОБ-языком (следствие из теоремы 4.3, лемма 4.1). Определим для каждого 1= 1, ..., и последовательность формальных рядов (являющихся многочленами). л<юе>, йкюн, ..., а<юю>, ... следующим образом: (!) д<юо> есть сумма свободных членов многочлена !ю> (П) й<ю+н полу. ! чается из ! подстановкой й<юю>, ..., д~ю> вместо $„..., $„ соответственно с последующим формальным раскрытием скобок и приведением подобных.
Непосредственно ясно, что для любых ю, ! (ю О, 1, ! = 1, ..., и) опорное мююожество ряда д<юю> есть Чю>. В то же время из наложенных на систему («) ограничений (1) — (3) следует, что каковы бы ни были ю = О, 1, ... и 1=1,..., а, коэффициенты при цепочках длины, НЕ бОЛЬШЕЙ Ю', ВО ВСЕХ рядаХ Л<ЮЮ>, Аю<ЮЮ+Н, д<ЮЮ+В>, ... СОВПадают. Действительно, цепочки длины, не большей единицы, в любом многочлеие л<юю> — это в точности свободные члены !ю длины 1; если утверждение справедливо для некоторого юо, то для юо + 1 оно вытекает из того очевидного факта, что каждая цепочка длины юо + 1 в многочлене д<юю+и при любых ю' и ! либо является свободным членом !ю, либо получается из некоторого члена !ю при подстановке вмеЬТО переменных каких-либо членов й<юю>, ...., д<ю>, являющихся цепочками длины, не большей !о, а такие члены у всех многочленов д<юю>, й)ю>ью>, д<ю+'>,...
по индуктивному предположению оди. иаковы. Таким образом, если обозначить через (! = 1, ..., Л) формальный ряд, в котором коэффициенты при каждой цепочке длины ю' (ю'=О, 1, ...) такие же, как в д<юю>, то к этому ряду будет сходиться последовательность л<юо>, а<>О, ... Однако опорное множество ряда я<о есть ю'.~ю'~, а предел неубывающей последовательности множеств*) равен объединению всех членов последова«) То есть такой, и которой каждый предыдущий член содержится в следующем. тельности.
Поэтому опорное множество ряда гю есть ю',ю. Что же касается коэффициента при (произвольной) цепочке х„ в ряде гю, то он, как легко понять, равен числу ($<, х„)-деревьев в соответствующей ОБ-грамматике, т. е. числу существенно различных способов вывода в этой грамматике цепочки х„из символа йю. В частности, для однозначной грамматики коэффициенты ряда г, принимают только значения О и 1. $ 6.5. Каноническое представление Б-языка Цель настоящего параграфа — доказать теорему, которая дает любопытное представление Б-языка, называемое иногда каноническим.
Предварительно введем некоторые определения. Пусть У вЂ” произвольный словарь, Уют и У.р- — подмножества У и Р— подмножество У'. Обозначим через ю'."(У, Уют, У«-, Р) множество тех цепочек в У, которые начинаются символами из Уюу, кончаются символами из У,ч- и содержат только такие подцепочки длины 2, которые принадлежат Р,— иначе говоря, 1.' (У, У,~, Уу., Р)= =УиУ" () У'Ул-() (У* — У'(1" — Р) У'). Ввиду теоремы 5.4 ю'.'(У, Ук, У,ч-, Р) является А-языком; мы будем называть такой А-язык с т а н д а р т н ы м.
Сопоставим далее каждому символу а 6= У «двойник໠— новый символ а ~ У вЂ” и определим два языка 0(У) и 1>'(У), которые будем называть соответственно языком Дика и скобочным языком, следующим образом: (!) пустая цепочка принадлежит обоим языкам; (й) если цепочки ху и х'у' принадлежат В(У) и 0'(У) соответственно, то для произвольного аеи У цепочки хаау и хану принадлежат юю(У), а цепочка х'аау' принадлежит А)'(У); (>й) никакая цепочка не может принадлежать ют>(У) или ю)'(У) иначе, как в силу (!) или (й).
Очевидно, язык Дика есть не что иное, как множество слов, равных единице в свободной группе с системой образующих У (если считать а и а взаимно обратными); скобочный язык, если интерпретировать а и а соответственно как левую н правую скобки с меткой а, будет представлять собой множество всевозможных «правильных последовательностей» скобок с метками из У.
214 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О В-ГРАММАТИКАХ [ГЛ. 6 Теперь мы можем сформулировать теорему. Те о р ем а 6.7. Для всякой Б-грамматики Г с основным словарем )! можно построить такой словарь Х:»!у и такой стандартный А-язык Е' в словаре, содержа- и!ем Х, что Е(Г) является проекцией пересечения 1.' П Р(Х) на Р и при этом Е' П Р(Х) = 1.' П Р'(Х), Д о к а з а т е л ь с т в о. Для упрощения конструкции будем считать, на что мы имеем право, что Г = = (!', %',1,)о) есть стандартная бинарная Б-грамматика.
Сверх того, допустим, что если для какого-либо символа В ~ В' имеется правило вида А - ВС, то не может существовать правила вида Е - гВ; требуемое для выполнения этого условия преобразование грамматики читатель проведет без труда. Символ В ее ЯГ будем назы-, вать «левым», соответственно «правым>, если имеются правила вида А — ВС, соответственно А — СВ. Занумеруем как-либо правила Г. Рассмотрим произвольную цепочку хееЕ(Г) и произвольную систему составляющих этой цепочки, отвечающую некоторому ее дереву вывода. Расставим в х скобки, отвечающие всем составляющим данной системы (включая тривиальные). Каждую скобку пометим тройкой (А,й !), где А †мет в узле, от которого «происходит» соответствующая составляющая, ! — номер правила, применяемого в данном узле, и ! — номер правила, применяемого в узле, подчиняющем данный; у сйпбок, ограничивающих полную составляющую, значение ! может быть произвольным, но непременно одинаковым для обеих скобок.
Левую и правую скобки с метками А, у, 1 будем писать в виде [А, С!1 и [А, ЕД соответственно. Далее вставим непосредственно справа от каждого вхождения символа а в цепочку х (левее ближайшей скобки) новый символ а — «двойника» а. Полученную цепэчку символов и скобок обозначим через х, а множоство всех таких цепочек (для всех х~ Е(Г)) — через Е. Имеем, очевидно, х = Прт х, так что Е(Г) = Прг Е.
Пусть, например, Г содержит правила: (1) 1- АВ, (2) А-+ а, (3) В-> Ь; тогда одна из возможных цепочек аЬ будет иметь вид [У, 3, 1][А, 1, 2]аа[А, 1, 2][В, 1, 3] ЬЬ [В, 1, 3][1, 3, 1]. О 66! КАНОНИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ В-ЯЗЫКА Е!5 Положим теперь Х = У [У Р', Ч = Р Ф 0 Р' [У 71', где !7 — множество «двойников» основных символов, а )и и Р' — соответственно множества (типов) левых и правых скобок, помеченных тройками, как описано выше.
Определим стандартный А-язык Е'=Е'(Р', Чв, Чв-, Р) следующим образом: а) Множества (св и )7в- будут состоять из всевозможных скобок вида [1, й у] и [1, й у] (с произвольными у, !) соответственно. б) Множество Р будет состоять из цепочек, сопоставляемых правилам Г следующим образом: б!) каждому правилу с номером уо, имеющему вид А- ВС, сопоставляются всевозможные цепочки [А ! 16] [В, уо, й], [В, уо й] [С уо 11 [С уо !1 [ А ! 16] где у, й, ! пробегают соответственно номера всех правил, номера всех правил с левой частью В и номера всех правил с левой частью С; б2) каждому правилу с номером уо, имеющему вид А- а, сопоставляется цепочка аа и всевозможные цепочки [А, й уо]а, а[А, й уо], где ! пробегает номера всех правил.
Покажем, что язык Е' не пересекается с множеством Р(Х) — Р'(Х). Действительно, пусть оо ~ Е' Й [Р(Х)— — Р'(Х)]. Поскольку цепочка оо принадлежит Р(Х), ее можно сократить до пустой цепочки, последовательно вычеркивая пары вида соа или аа, где а ее Х. В то же время оо ф Р'(Х); поэтому при сокращении хоти бьг один раз должна быть вычеркнута пара вида аа, иначе говоря, оз должна содержать надцепочку вида а5а, где Е сокращается до пустой цепочки. Цепочку $ можно выбрать так, чтобы при ее сокращении никакая пара вида ]]б не вычеркивалась. [Если $ этим свойством не обладает, то она содержит подцепочку йЩ где $, сокращается до пустой цепочки; если $, еще не обладает нужным свойством, то она содержит подцепочку такого же вида, и т. д.] Пусть цепочка $ такова; она не может быть пустой, поскольку из самого определения языка Е' ясно, что его цепочки подцепочек вида асо не содержат.
Следовательно, $ имеет вид ~т)у, где р, у ~Х. Поскольку ненадчеркнутый символ е стоит непосредственно справа от надчеркнутого символа а, должно быть со = [В, у, й]„р = [С, у, !], причем в Г найдется правило $6.61 2!З ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6 кхноническое пеедстхвление е.языкА 2!7 вида А- ВС (действительно, по определению языка Е' всякая подцепочка всякой его цепочки, имеющая вид ай, именно такова), так что С вЂ” правый символ, а В— левый.
Однако совершенно аналогичным образом из того, что а стоит непосредственно справа от у, получается, что символ В правый. Имеем противоречие. Таким образом, Е' П [Р (У) — Р'(2)] = Ы, т. е.Е' П Р (2) = = Е' П Р'(Я). Следовательно, нам достаточно теперь доказать, что Е = Е'П Р'(2). Однако из способа построения цепочек х непосредственно ясно, что каждая такая цепочка принадлежит как Е', так и О'(Л). Остается показать, что любая цепочка Ч~~Е'ПР'(Л) принадлежит Е. Для этого мы воспользуемся индукцией по длине 6р, причем для удобства проведения индукции будем доказывать несколько более общий факт.
Сопоставим каждому символу А Ен !г" стандартный А-язык 6 ЕА, отличающийся от Е' только тем, что К,г и будут состоять теперь из всевозможных скобок вида ' [А, Е 1] н [А, Е1] соответственно. Обозначим через ЕА(Г) множество всех цепочек в Г', выводимых в Г из А; для каждой цепочки хее Е„(Г) построим х так же, как это делалось для цепочек из Е(Г), и множество всех таких х обозначим ЕА. Покажем теперь, что для любого А~)г" всякая цепочка Ч~~ЕА() Р (2) принадлежит ЕА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
