Гладкий - Формальные грамматики и языки - 1973 (947381), страница 39
Текст из файла (страница 39)
Пусть р!, рг,, й» вЂ” все отличные от а левые узлы т', упорядоченные сверху вниз, и а = аа, аь ..., ад — все остальные узлы т', упорядоченные так же (рис. 13). Обозначим через Ч'ь 6; метки при а», р! соответственно и через В, А»... А,— те символы из Уь вхождениям которых в Х соответствуют вхождения 6м»Р», ..., Ч'! в и(Т'), отвечающие узлам [3м ад, ..., а! дерева Т' (в этом порядке). Тогда Х представляется в виде Х = У!ВАд...А!Уг, Категории Ч"и .. Ч"», 6» принадлежат /'(А!), ..., /'(А»), /'(В) соответственно. По предыдущему, категории 6!, ..., 6!, элементарны, а Ч"ь ..., Ч"д неэлементарны; категория Ч'д либо неэлементарна, либо равна Фгл кроме того, Ч"! = [6![Ч'о[ и Ч"! — — [6М!-![ при ! =4, ..., й.
Заметим, что % — правая Апкатегория, так как «числитель» неэлементарной левой категории всегда является элементарной категорией, отличной ог Ф». Обозначим теперь через 1 наибольшее из чисел г, ... ..., й, для которого Чг! есть правая Агкатегория, и через т" — полное р! !.поддерево Т' (если 1= 1, считаем р! ! — — а). Положим Т! = ЗпЬ(Т', г", 6! !). «Числитель» правой категории — левая категория; поэтому найдется такое В ен )У!, что 6! ! является левой В-категорией.
Если положить Х! = У!ОА! !...'А!Уг, (при 1= 1 пола- р .!з гаем Х! — — У!Руг), то !((Т!) будет цепочкой категорий, сопоставляемой цепочке Х! функцией /'. Отсюда, по индуктивному предположению, следует, что Х! выводима из / в Г. Поэтому для завершения доказательства достаточно установить, что цепочка ВА»А» !...А! выводима в Г из Р. Поскольку 6» — элементарная В-категория, а %» Ч'» „ ..., Ч"»+, — неэлементарные левые Ад-, Ад,-...„ ..., А,+,-категории, они имеют соответственно вид С" [В»»1С~~»1, [В~~»-!!~С»д !!~, ..., [!В,"!«ЯС~г+! ![, где С, Р, Вь Со Р,~ЮГ. Но из равенства Ч"д — — [6»!6» ![ получаем С" =В„"д.
Далее из того же равенства вместе с равенством Ч"», =[6» !16 [ следУет Сд»=Вг!'Т! и т. д. Имеем, таким образом: 6» =В», Ч"» =[В»'!Вд-![, Ч!»-!= = [В»-ЙВ»-г[, °, %+! = [Вц".![С~!»![. Отсюда, поскольку 6» — В-категория и Ч', — А,-категория, вытекает наличие в /7 правил Р-«ВВ», В»-«А,В» !, Вд, — «А»,В» ь ... ..., В!+, — «А!.„,С!+и что дает Р 1-ВА»Ад ! .. ° А!+!Сг+!, г В то же время %=[6!!6с-![=[С!+!16! !~, и % пра вая Аикатегория, а 6с, — левая 0-категория; но это в силу определения правой Агкатегории дает С,+, — — А! и Р=В.
Итак, /У 1- ВА»Ад, ... Аь Доказательство закончено. г Подведем итог. Будем называть сложностью катее г о р и и общее число вхождений в нее символов ! и / и сложностью К гр ам м ат и к и — максимальную сложность категорий, входящих в значения ее приписывающей функции. Кроме того, назовем К-грамматику левосторон ней (правосторонней), если категории, входящие в значения ее приписывающей функции, не содержат вхождений символа / (соответственно!). В последнем рассуждении мы имели дело с левосторонней грамматикой сложности, не превосходящей 2; ничто не помешало бы нам, разумеется, повторить это рассуждение для правосторонней грамматики.
Суммируя, получаем следующую теорему. Теорем а 6.1. а) Для всякой К-еримматики можно построить эквивалентную ей Б-гриммпгику. б) Длл вся- 7$ 196 дополнитнльныв сввдвиия О в-ГРАммАтиклх [гл, А ПОРмлльиАЯ ФОРМА,в.гРлммхтики кой Б-грамматики маекно построить эквивалентную ей левостороннюю (правосгороннюю) К-грамматику сложности, не превосходящей 2. С л е д с т в и е. Для всякой К-грамматики можно построить эквивалетную ей левостороннюю (правостороннюю) К-грамматику сложности, не превосходящей 2. Замечания, 1.
В теореме 6.1,б) нельзя заменить двойку единицей (упражнение 6.4); это невозможно и при отказе от односторонности (упражнение 6.5). 2. Назовем путь ам аь ..., и, в бинарном дереве л евым (правым), если узлы аь ..., а, левые (правые). Если ар, ссь ..., а,— правый путь в дереве сокращения левосторонней К-грамматики и узел ае помечен категорией '1гм то метка при а1 будет иметь вид [Чг~~Ч"о), метка при аз — вид (Ч'А'1(%'1ЧЯ и т.
д. Поэтому длина правого пути в дереве сокращения левосторонней К- грамматики не может превосходить сложности этой грамматики; аналогично для левых путей в деревьях сокращения правосторонних грамматик. Отсюда по теореме 6.1 получаем, переходя к канонически соответствующей Б-грамматике, что для всякой Б-грамматики Г можно построить эквивалентную ей стандартную бинарную Б-грамматику Г' такую, что длины праных (левых) путей в деревьях полных выводов в Г' не превосходят 2. $6.2. Нормальная форма Б-грамматики Замечание 2 к теореме 6.1 мы используем для доказательства следующей теоремы о Б-грамматиках, Теорем а 6.2 (теорема о нормальной форме). Для всякой Б-грамматики можно построить эквивалентную ей Б-грамматику, все правила которой имеют один из следующих видов: А-+а, А- аВ, А-~.аВС, где А, В, С вЂ” вспомогательные символы и а — основной символ.
Доказательство. Пусть Г'= (Уе, (Р'А,Р,В')— стандартная бинарная Б-грамматика. Будем сопоставлять символам из (УА (не обязательно всем) числа, которые назовем их левыми степенями, следующим образом: (1) левая степень считается равной нулю для тех А ~ )Р'е, для которых не существует правил вида АВС (так что всякое правило с левой частью А имеет вид А — а, где а е=- Уе); (й) если для каждого й = О..., ..., и — 1 определено понятие символа левой степени й, то символу А я )УА приписывается левая степень п, если ему не приписано в качестве левой степени ни одно из чисел О, ..., и — 1 и в каждом правиле вида АВС, В, С ~ (ре, символ В имеет левую степень, меньшую и.
Если всем символам из )УА можно приписать левые степени и наибольшая из них равна 1т', будем называть ГА грамматикой левой степени У. Ясно, что если ГА— приведенная грамматика, то она имеет левую степень У тогда и только тогда, когда )т' есть точная верхняя граница длин левых путей в деревьях полных выводов в ГА Пусть теперь à — произвольная Б-грамматика с основным словарем У. По замечанию 2 к теореме 6.1 можно построить эквивалентную Г стандартную бинарную Б-грамматику 1'= (У,)У',В,В') такую, что длины левых путей в деревьях полных выводов в Г' не превосходят 2.
Перейдем от Г' к эквивалентной приведенной грамматике ГА = (У )Р 1А В'), где Я7': — (У' и ВА: — В' (лемма 4.8). При этом множество деревьев полных выводов не изменится, и по предыдущему Г' будет грамматикой левой степени, не превосходящей 2. Пусть г = А — ВС еп В', Тогда левая степень символа В равна О или 1. Сопоставим правилу г всевозможные правила вида А — ЬС, где Ь я У и В- Ь ен Ве, а если левая степень В равна 1,— еще и всевозможные правила вида А- Ь~ВАС, где Ь1 н Вз удовлетворяют условию епУЬВзе(УАЬ й (Э В, еи 'йГА) (В -+ В, Вз еп йс а В, -+ Ь, ~ )лв] Если заменить в Г' каждое правило вида А — ВС совокупностью сопоставленных ему новых правил, то полученная грамматика будет, очевидно, эквивалентна ГА, а следовательно, и Г.
Доказательство закончено. Грамматика, удовлетворяющая требованию теоремы 6.2, называется Б-грамматикой в н о р м а л ь н о й форме Грейбах (или просто в нормальной форме). Теорему 6.2 можно усилить следующим образом, !99 нОРМАльнАя ФОРМА е ГРАммзтики [93 ЛОНОлнительные сведения О е-ГРАммАтикАх [Гл. з Те о р е м а 6.3. 41[ля всякой Б-грамматики Г и всякого целого положительного числа я можно построить Б-грамматику Г' =([г, 1[", 1', 14'), эквивалентную Г, всг правила которой имеют один из следующих видов; 'А — » х, А — » уВ, А — уВС, где А, В, С я ))7', х, у ее)г+, 1 х [(я, [у != я. Доказательство.
Пусть Г=(Р', [[[г, 1, 11)— Б-грамматика в нормальной форме, Если А я 'й[г, х я 1г+, [х ~ = я, Х ~ )ч" и цепочка хХ выводима в Г из А, то [Х )(я+ 1. Сопоставим каждой цепочке Х ~ ))г+, [Х)- я+1, новый символ 6(Х); совокупность всехтаких символов обозначим [4«'. Пусть Г'= ()г, [«", [1(1), 11'), где ')(' состоит из всевозможных правил следующих видов: 1) 6(А, ... АА)-» х„где 1 ~ ~й ( я + 1; ~ х [ ( я; А, ... АА [-х[ Г 2) р(А, ... Аз)- уб(А[+[ ... А„), где 1(1<14( (~я+1;(у~=я; А, . А[ 1 — у; г 3) 6(А[ ... Аз) — »иоб(х)р(АН»[ .. АА), где ! (1< < й ( я + 1; ~ ио ~ = я; У ~ )[7+; А, ... А[, [- и; А, [ — ОХ; г г 4) 6(А, ...
АА) — » ив[1(2), где 1(й (я+1; [ио [=я; Х ~ ))7+; А, ... АА, [- и; АА [ — ОХ. г г Эти правила строятся по 11 эффективно. Легко видеть, что Г' эквивалентна Г. Теорему 6.3 мы используем для доказательства следующего утверждения о МП-машинах. Теор е м а 6.4. Для всякой МП-машины М можно построить эквивалентную ей МП-машину Лд', обладающую тем свойством, что ни в одном ег вычислении ни разу не выполняются подряд два элементарных шага на рабочей ленте (иначе говоря, между каждыми двумя «рабочими» шагами читается хоть один входной символ).
Дока за тельство. При построении машины М' мы можем отправляться не от МП-машины М, а От Б-грамматики Г = ()г, )[г,1,К) и при этом имеем право считать, что Г удовлетворяет требованию теоремы 6.3 прн я = 3. Входным и рабочим алфавитами М' будут )г и )[7 соответственно. Программа М' будет представлять робой объединение систем инструкций, сопоставляемых правилам,Г указываемым далее способом, с добавлением инструкций д[че- д, д~- дз. Сопоставление правилам систем инструкций производится следующим образом: 1) правилу вида г=А- а(а ее)г) сопоставляется система [да- д,(г), Ад,(г) — »д); 2) правилу вида А-»а,а,(а„а, ~[г) сопоставляется система (да,- д,(г), д, (г) а,— д,(г), Ад,(г) — д); 3) правилу вида А- а,азаз(ан аз, азее)г) сопоставляетсясистема [да,— д,(г), д, (г) аз-»д,(г), д,(г) аз-»дз(г), Адз(г)- Ч)' 4) правилу вида А-» а,а,азВ(а„а,, а„~ )г; В ~1[7) сопоставляется система (Ча, — » д, (г), Ад[ (г) -» Чз (г), д,(г) а, д, (г), Ч,(г) ВЧ, (г), Ч (г) аз д)[ 5) правйлу вида А — а[азазВС(а„аз,аз е [г; В, С е— : [[г) сопоставляется система (да, -4 д, (г), Ад, (г) -» дз (г), Чз (г) аз» Чз (г) Чз(г)» СЧ4 (г) Ч4 (г) аз» Чз(г) дз(г)» ВЧ)' Здесь д[(г) — состояния, различные при разных 1 н при разных г.
Единственным заключительным состоянием является до. Из самой конструкции ясно, что каждое вычисление машины М' удовлетворяет нужному условию. Эквивалентность 1' и М' доказывается без труда; мы предоставляем это читателю. [У к а з а н и е. Между вычислениями М' и упорядоченными размеченными выводами в Г устанавливается соответствие таким образом, что каждой промежуточной цепочке вывода, имеющей вид хХ, где х а У-, Х ен )[74, отвечает участвующая в вычислении ситуация, при которой прочитанная часть входной цепочки есть х, а на рабочей ленте записана цепочка Х.] 3 а м е ч а н и я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
