Гладкий - Формальные грамматики и языки - 1973 (947381), страница 24
Текст из файла (страница 24)
Индукцией по » легко показать, что каждое Т» есть дерево вывода, отвечающее размеченному выводу («В «, »ь'„... ..., »ь» „»ь»), так что, в частности, Т отвечает 0'. Итак, каждой допустимой последовательности невисячих узлов Т отвечает размеченный вывод Р'. При этом ясно, что различным допустимым последовательностям соответствуют различные размеченные выводы. Картина будет завершена, если мы покажем, что любой размеченный вывод, отвечающий данному дереву Т, может быть получен таким способом. Чтобы убедиться ' в этом, рассмотрим размеченный вывод 0' =(е', а», ... ..., ь»' », вь), где е' = » В «, н «сожмем» соответствующее растянутое дерево Т', как описано в з 3.1.
Узлами полученного дерева Т будут классы узлов Т', причем каждый класс состоит из узлов, лежащих на одном пути, и при этом каждое вхождение»ь',, !=О, ..., Ь вЂ” 1, является «младшим» (самым далеким от корня) узлом » 4.»1 НЕКОТОРЫЕ ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ 1!9 в некотором классе, отвечающем невисячему узлу Т, Если теперь обозначить через Е» тот узел Т, для котоого младший узел соответствующего класса есть»ь» „ Р то последовательность Еь ,, ЕА будет, как легко видеть, допустимой, и размеченный вывод, полученный по этой последовательности описанным выше способом, совпадает с Р'. Полезно заметить, что среди размеченных выводов, отвечающих данному дереву вывода, всегда есть один и только один упорядоченный. С другой стороны, упоряочиваемому выводу в Б-грамматике отвечает единстдочи венный упорядоченный размеченный вывод.
Таким обрб азом, между деревьями вывода и упорядочиваемыми выводами в Б-грамматике имеется взаимно однознач ное соответствие. Пр и м е р. Пусть В-грамматика Г содержит правила А — 4 а В А, В -+ ВВ, А -+ ВА,  — О, В -+ Ь, 0 — » сд, А -+ а. Тогда размеченному выводу (*А«, а«В «А, аВВ «А*, и»«ВА, а«В»РВА, аЬ*Р»ВА, аЬс»1*В«А, абс»(Ь» А», аЬсдЬа) будут отвечать дерево вывода, изображенное на рнс. 3 (стр. 81), и растянутое дерево вывода на рис.
2; это последнее дерево соответствует следующей допустимой последовательности невисячих узлов первого (обозначенных цифрами, стоящими на рис. 3 в скобках): 1, 2, 3, 5, 4, 8, 6, 7. Другой допустимой последовательйости: 1, 3, 7, 6, 2, 5, 4, 8 — отвечают растянутое дерево на рис. 5 и размеченный вывод («А*, аВ«А«, аВВ«А*, аВ*В*а, а«В»Ьа, аВ«В*Ьа, а» В«ОЬа, аЬ*Р*Ьа, аЬс»(Ьа). Приведем еще несколько простых соображений, относящихся к деревьям вывода. Л е м м а 4.4. Пусть Π— вывод в Б-грамматике Г, Т вЂ” его дерево, Ь вЂ” длина О, з — высота Т и д— максимум длин правь»х частей правил Г. Тогда з(Ь < <~ гелий)1,из=й,гелий=1. Д о к а з а т е л ь с т в о. Первое неравенство очевидно; второе следует из того, что Ь равно числу невисячих узлов Т и из каждого узла Т исходит не более д дуг.
Равенство з = Ь при и = 1 очевидно. Будем называть (В, в») -дерево п р о с т ы м, если в нем никакие два различных невисячих узла, лежащих Рис. 3, '120 в-ГРАммАтики и МАшины с мАГАзиннои пАмятью [Гл, я .на одном пути, не помечены одним и тем же символом, (В, в)-дерево, всякое собственное полное поддерево которого простое, будем называть к в а з и п р о с т ы м. А (П ол но е (6-) поддерево Рндерева Т вЂ” это Р,-поддерево Т, образованное всеми узлами, в которые идут пути из данного узла 6.) Очевидна счедующая Л е м м а 4.5. Высота простого (квазипростого) (В, [ь)-дерева в Б-грамматике Г не превосходит р (соответственно р + 1), где р — мощность вспомогательного словаря Г.
В заключение введем операцию над деревьями вывода, которая будет нам весьма полезна при изучении Б-грамматик. Пусть Т = (М; ~, (, д) есть (А, н)-дерево, р — какой-либо узел Т, Š— составляющая цепочки [ь, соответствующая узлу р (в системе составляющих, определяемой деревом Т), и $ [р «ц — соответствующее этой составляющей вхождение подцепочки в Гь. Пусть, кроме того, д(6) = В. Обозначим через Т~ полное Р;поддерево дерева Т с корнем в р; очевидно, Т~ есть (В, ф-дерево. Рассмотрим теперь произвольную цепочку ~р, выводимую из В, н произвольное (В, ф)-дерево 444[ РАспознквкннв птстоты н конвчности вязыкА' Тм и обозначим через БНЬ (Т, Ть Тг) Рндерево, полученное из Т «вырезанием» поддерева Т, н подстановкой на его место ТА.
Ясно, что БНЬ (Т, Ть Тг) является (А, $ч[т[)-деревом, и в соответствующей системе составляющих для цепочки ЭЧ[[1 узел 11 дает составляющую, отвечающую вхождению $ «ф«[1 подцепочки ф. ф 4.2. Распознавание пустоты и конечности Б-языка Проекции Пусть Г =(У, я7, 7,В) — Б-грамматика, А ен 1Г, аен ен У 0 (Р. Будем говорить, что а з а в и сит от А, если нз А выводима в Г хотя бы одна цепочка, содержащая вхождение а.
Л е м м а 4.6. Существует алгоритм, позволяющий по любой Б-грамматике Г = (У„яг, 7, й) и любым двум символам А ен Я7, сс ен У() %7 распознать, зависит ли а от А. Доказательство. Пусть в Б-грамматике Г= =(У, %,1, )Г) существуют выводы вида (А = шо, ... ..., [ЯА = бац). Возьмем тот из этих выводов, чье дерево содержит меньше всего узлов (еслн таких деревьев несколько, берем любое из них), и обозначим это дерево через Тя. Среди висячих узлов Т, хотя бы один помечен символом а. Пусть уь, уь ..., у.— путь из корня Ть в этот узел, Все узлы Тм не лежащие на этом пути, являются висячими.
Действительно, в противном случае для некоторого 1, 1 = О, ..., з — 1, какой-либо узел 6, подчиненный у; и отличный от у,+н будет невисячим; но тогда дерево БНЬ(Т,, Т', Т"), где Т' — полное 6-поддерево Ть и Т" — дерево, состоящее нз одного узла 6, будет деревом некоторого вывода, начинающегося символом А и заканчивающегося цепочкой, содержащей вхождение а, н это дерево будет содержать меньше узлов, чем Ть Далее, при [ <1 узлы у[ и у; не могут быть помечены одним и тем же символом, иначе дерево БНЬ(ТА, Т1', Тз), где Т' и Т[ — полные уа и упподдеревья Ть соответственно, также было бы деревом вывода из А цепочки, содержащей а, и имело бы меньше узлов, чем Т,. Поэтому з ( [А(Й'); но е есть как раз число невисячих вершин Ты т.
е. длина соответствующего вывода. Теперь искомый алгоритм очевиден — достаточно [йй В-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4 $4СЕ РАСПОЗНАВАНИЕ ПУСТОТЫ И КОНЕЧНОСТИ В-ЯЗЫКА [Уз перебрать все выводы в Г, длины которых не превосходят )4(%'). Назовем вспомогательный символ Б-грамматики Г б е с и л о д н ы м, если из него не выводима никакая цепочка в основном словаре Г. Л е м и а 4.7.
Существует алгоритм, позволяющий по любой Б-грамматике Г и любому ее вспомогательному символу А распознать, является ли А бесплодным. Д о к а з а т е л ь с т в о. Пусть Г = ()', ((У, 1, )г)— Б- -грамматика, н для некоторого символа А ~ ((У существуют выводы, начинающиеся данным символом и заканчивающиеся цепочками в (г.
Возьмем тот из этих выводов, чье дерево — обозначим его Те — содержит меньше всего узлов (еслн такое дерево не одно, то берем любое). Дерево Те будет простым. В самом деле, если это не так, то в нем найдется путь 6[, бь ..., 6„такой, что 6[ и б„помечены одним и тем же символом и 6„— невисячий узел; но тогда дерево Бп)э(Те, Т', Т"), где 7' и Т" — полные 6[- и б,-поддеревья Тп соответственно, будет содержать меньше узлов, чем Те, и тоже будет деревом вывода, начинающегося символом А и заканчивающегося цепочкой в (г. По лемме 4.5 высота Те не превышает )4(((У), откуда по лемме 4.4 можно найти верхнюю границу для длины соответствующего вывода.
Искомый алгоритм состоит, таким образом, в переборе всех выводов в Г, длины которых не превосходят этой границы, Поскольку бесплодность начального символа Б-грамматики означает пустоту порождаемого ею языка, из леммы 4.7 вытекает Теор ем а 4.1. Существует алгоритм, позволяющий по любой Б-грамматике Г распознать, является ли язв[к 1.(Г) пустым. Пусть Г =((1, ((У, 1, Л) — Б-грамматика и Я с= )1. Символ А е: — ((У мы будем называть Е-бе сп л одным, если из него не выводима никакая цепочка в словаре Я, Буквальным повторением рассуждений, примененных при доказательстве леммы 4.7, получается Л ем м а 4.7'.
Существует алгоритм, позволяющий по любой Б-грамматике Г =((1, ((У,1,)г), любому словарю л с= (1 и любому символу А ы ((У распознать, является ли А Х-бесплодным, Назовем вспомогательный символ Б-грамматики Г н е у с т р а н и м ы м, если он а) зависит от начального символа или совпадает с ним и б) не бесплоден.
В противном случае вспомогательный символ будет называться устр а н им ы м. Б-грамматику, все вспомогательные символы которой неустранимы, будем называть приведенной. Л е м м а 4.8. Для всякой Б-грамматики Г = =((г, (эг,1,)г), порождающей непустой язык, можно построить эквивалентную ей приведенную Б-грамматику Г = ()г, ((У', 1, )(') такую, что ((У' с= ((У и )(' с= )(. Д о к а з а тел ь ство.
Из определения ясно, что ни один узел дерева полного вывода не может быть помечен устраинмым вспомогательным символом. Поэтому, выбросив из вспомогательного словаря все устранимые символы, а из схемы — все правила, содержащие эти символы в левых или правых частях, мы не изменим порождаемого грамматикой языка. Полученная так грамматика не обязана еще быть приведенной*), но в случае надобности к ней можно применить такое же преобразование, затем так же преобразовагь следующую грамматику и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
