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