Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 64
Текст из файла (страница 64)
Окончательная НФХ-грамматика показана на рис. 7.3. 7.1. НОРМАЛЬНЫЕ ФОРМЫ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 281 Š— ь ВС, ! ТСз ! ЬСз ! а ! Ь! 1А ! 1В ) 12 ! Ю Т вЂ” ь 7Сз ! ЬСз ! а ! Ь | 1А ! 1В ! 12 ) Ю Р -+ ЬС, ! а ! Ь |!А ) 1В ! 1е ( Ю 1 — э а ) Ь | 1А (!В ! 12 ! 1О А — ьа  — +Ь Е вЂ” >О О-+1 Р— >ь М вЂ” >* Ь вЂ” э( В-э) Сз — > РТ Сз -+ МР Сз — + ЕВ Рис.
7 3. Преобразование тел к одинонньив терминалом или двум неременным Теорема 7.!6. Если Π— КС-грамматика, язык которой содержит хотя бы одну не- пустую цепочку, то существует НФХ-грамматика Он причем ЦОз) = 1(О) — ( в). Доказательс~во. По теореме 7.14 можно найти КС-грамматику Оь для которой ЦОз) = Ь(О) — ( г), причем Оз свободна от бесполезных символов, цепных и в-продукций.
Конструкция, преобразующая Оз в НФХ-грамматику Оз, изменяет продукции таким образом, что каждая продукция из Оз может быть пронмитирована одной или несколькими продукциями из Он Наоборот, каждая из введенных в Оз переменных соответствует лишь одной продукции, поэтому эти переменные можно использовать только надлежащим образом. Более строго, докажем, что ге н 1(Оз) тогда и только тогда, когда и н ЦОз). (Необходимость) Если н порождается в Оп то легко заменить каждую использованную продукцию, скажем, А -+ХХз,..Хь последовательностью продукций из Ор Таким образом, один шаг порождения в Оз превращается в один или несколько шагов в порождении и, использующем продукции Оз.
Во-первых, если Х, — терминал, то Оз имеет соответствующую переменную В, и продукцию В, -+ Хь Во-вторых, если /с > 2, то Оз имеет продукции А — э В,Сь С, -+ ВзС. и так далее, где В, есть либо переменная, введенная для терминала Хь либо сам Хь если это переменная. Эти продукции имитируют в Оз один шаг порождения в Оз, использующий продукцию А э Х,Х,...Хл.
Делаем вывод, что в Оз существует порождение и, поэтому зе н ЦОз). (Достазпочность) Предположим, что ге ц 1(Оз). Тогда в Оз существует дерево разбора с отметкой корня 5 и кроной н. Преобразуем это дерево в дерево разбора в Ол также имеющее отметку корня 5 и крону н. ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 282 Сначала "сделаем откат" части б построения НФХ. Предположим, существует узел с отиеткойА и сыновьями, отмеченными В~ и Сн где Сз — одна из переменных, введенных в части б.
Тогда данная часть дерева разбора должна выглядеть, как на рис. 7.4, а. Поскольку каждая из зтнх введенных переменных соответствует лишь одной продукции, существует только один способ для их возникновения, и все эти переменные, предназначенные для обработки продукции А -ь В,В,...Вь должны появляться вместе (см. рис. 7.4, а).
Каждый такой куст узлов в дереве разбора можно заменить продукцией, которую они представляют. Преобразование дерева разбора показано на рис. 7.4, б. Полученное дерево все еще не обязательно является деревом разбора в Сз. Причина в зви, что на шаге а построения НФХ были введены другие переменные, порождающие а) б) Рис. 7.4 Дерево разбора должно использовать введенные переменные спелиальным образом 7.1. НОРМАЛЬНЫЕ ФОРМЫ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 283 одиночные терминалы. Однако их можно обнаружить в полученном дереве разбора и заменить узел, отмеченный такой переменной А, и его единственного сына, отмеченного а, одиночным узлом с отметкой а. Теперь каждый внутренний узел дерева разбора образует продукцию бл и мы приходим к выводу, что и е ЦС~).
П Нормальная форма Грейбах Существует еще одна интересная нормальная форма для грамматик, которая не будет обоснована. Любой непустой язык, не включающий я, есть ЦС) для некоторой грамматики С с продукциями вида А — > асг, где и — терминал, а а — цепочка из нуля или нескольких переменных. Преобразование грамматики к этой форме является сложным, даже если задачу упростить, скажем, начав с НФХ-грамматики. Иначе говоря, первая переменная каждой продукции расширяется до тех пор, пока не будет получен терминач, Однако на этом пути возможны циклы, в которых терминач не достигается, и этот процесс необходимо "замкнуть".
Для того чтобы породить все последователь- ности переменных, которые могут появиться на пути к порождению этого терминала, создается продукция с терминалом в качестве первого символа тела и переменными вслед за ним. Эта форма, называемая нормальной формой Грейбах, по имени Шейлы Грейбах (эйе11а Огейбасй), которая первой дала способ построения таких грамматик, имеет несколько интересных следствий. Поскольку каждое использование продукции вводит ровно один терминаз в выводимую цепочку, цепочка длины л порождается в точности за л шагов. Кроме того, если применить конструкцию из теоремы б.!3 для построения МП-автомата по грамматике в нормальной форме Грейбах, то получается МП-автомат без г-переходов, показывающий, что такие переходы в МП-автомате всегда можно удалить.
7.1.6. Упражнения к разделу 7.1 7.1.1. (я) Найдите грамматику, не содержащую бесполезных символов и эквивалентную следующей грамматике.  — э ВСТ АВ С-э аВ~Ь 7.1.2. Рассмотрите следующую грамматику: 5 — гАВВ~г А — > аАВ, 'а  — ~ ВЬВ ~ А ~ ЬЬ а) удалите я-продукции; ГЛАВА 7. СВОЙСТВА КОНТККСТНО-СВОБОДНЫХ ЯЗЫКОВ 7.1.3. 7,1А. 7.1.5. 7.1.6. 7.1.7. 7.1йй 7.15ь б) удалите цепные продукции; в) есть ли здесь бесполезные символы? Если да, удалите их; г) приведите грамматику к нормальной форме Хомского. Выполните упражнение 7.1.2 со следующей грамматикой. 5-+ ОАО ! !В! ! ВВ А -э С В-э5!А С->5! е Выполните упражнение 7.1.2 со следующей грамматикой.
5-эААА ! В А — э аА !   — >е Выполните упражнение 7.1.2 со следующей грамматикой. 5-~аАа!ЬВЬ|в А-эС)а  — >С)Ь С вЂ” > СГзЕ! е 0 — э А ! В ! аЬ Постройте НФХ-грамматику для множества цепочек сбалансированных скобок. Можно начать с грамматики, находящейся в НФХ. (!!) Пусть С вЂ” КС-грамматика с р продукциями и длины тел продукций не пре- восходят л. Докажите, что если А =» ц то найдется порождение л из А, в котоо ром не более, чем (и' — 1)/(л — 1) шагов. Как близко можно на самом деле подой- ти к этой границе? (!) Предположим, что нам дана грамматика 0 с л продукциями, ни одна из которых не является е-продукцией, и мы преобразуем ее в НФХ: а) докажите, что НФХ-грамматика имеет не более, чем О(п ) продукций; б) докажите, что у НФХ-грамматики число продукций может быть прямо про- 3 порциональным и.
Указание. Рассмотрите конструкцию удаления цепных продукций. Дайте индуктивные доказательства, необходимые для завершения следукпцих теорем: а) часть теоремы 7.4, в которой доказывалось, что обнаруживаемые символы действительно являются порождающими; 7,1. НОРМАЛЬНЫЕ ФОРМЫ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 285 б) теорема 7.6 в обе стороны, где доказывалась корректность алгоритма из раз- дела 7.1.2 для обнаружения достижимых символов; в) часть теоремы 7.! 1, где доказывалось, что все обнаруженные пары действительно являются цепными парами, 7.1.10.
(а!) Можно ли для каждого КС-языка найти грамматику, все продукции которой имеют вид или А — з ВСР (тело состоит из трех переменных), или А — з а (тело образовано одиночным терминалом)? Приведите либо доказательство, либо контрпример. 7.1.11. В этом упражнении показывается, что для каждого КС-языка Е, содержашего хотя бы одну непустую цепочку, найдется КС-грамматика в нормальной форме Грейбах, порождаюшая  — (к). Напомним, что тела продукций грамматики в нормальной форме Грейбах (НФГ) начинаются терминалом. В построении используется ряд лемм и конструкций.
!. Пусть КС-грамматика 6 имеет продукцию А — ~ ггВД и всеми продукциями для В являются  — з у~ ! у ! ... ( у„. Заменив А э ггВ)3 всеми продукциями, у которых вместо В подставлены тела всех В-продукций, получим А э ау Д ! ау!3 ! ... ! ауя3. Построенная грамматика порождает тот же язык, что и гэ. Далее будем предполагать, что грамматика 6 для В находится в нормальной форме Хомского, а ее переменные обозначены Ан Ал ..., Аь 2. (*!) Докажите, что путем повторных применений преобразования из части 1 грамматику П можно превратить в эквивалентную грамматику, у которой тело каждой продукции для А, начинается или терминалом, или А, для некоторогоу > ь В обоих случаях все символы после первого в теле продукции— переменные.
3. (!) Пусть б~ — грамматика, полученная из б путем выполнения шага 2. Пусть А, — произвольная переменная и А, — э А,а, ! ... ~ А,а — все Ар продукции, тело которых начинается с А,. Пусть А, -з В, ! ... ! Д, — все остальные Арпродукции. Заметим, что каждое Д начинается либо терминалом, либо переменной с индексом больше б Введем новую переменную В, и заменим первую группу из гл продукций следуюшими; А, — з )3, ( ... , ')3р В, — з а В,! а, ! ., ! гг В,! а Докажите, что подученная грамматика порождает тот же язык, что и О или 6л 4.
(в!) Пусть после шага 3 получена грамматика С'> Отметим, что тела всех А; продукций начинаются или терминалом, или А, с 3'> ~'. Кроме того, тела Вг продукций начинаются или терминалом, или некоторым Ар Докажите, что Пз имеет эквивалентную грамматику в НФГ. Указание. Сначала преобразуй- 288 ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ те должным образом продукции для Ам затем для А», и так далее до Аь используя часть 1. Затем снова с помощью части 1 преобразуйте продукции для В, в любом порядке.
7.1Д2. Используйте построения из упражнения 7.1.11 для преобразования в НФГ слелующей грамматики. л-+АА )0 А -+Ю) 1 7.2. Лемма о накачке для контекстно-свободных языков В этом разделе развивается инструмент доказательства, что некоторые языки не являются контекстно-свободными. Теорема, называемая "леммой о накачке для контекство-свободных языков"', гласит, что в любой достаточно длинной цепочке КС-языка можно найти две близлежащие короткие подцепочки (одна из них может быть пустой) и совместно их "накачивать".
Таким образом, обе подцепочки можно повторить! Раз для любого целого б и полученная цепочка также будет принадлежать языку. Эта теорема отличается от аналогичной для регулярных языков (теорема 4.1), гласящей, что всегда можно найти одну короткую цепочку для ее накачки. Разница видна, есяв рассмотреть язык типа А = (О" 1" ~ н> 1). Можно показать, что он нерегулярен, если мфнкснровать л н накачать подцепочку из нулей, получив цепочку, в которой символов 0 больше, чем 1. Однако лемма о накачке для КС-языков утверждает, что можно найти две короткие цепочки, поэтому нам пришлось бы использовать для накачки цепочку из пулей и цепочку из единиц, порождая таким образом только цепочки из Ь.
Этот резуль»вт вас устраивает, так как». — КС-язык, а для построения цепочек, не принадлежащих юыку Ь, лемма о накачке для КС-языков использоваться и не должна. ?.2Д. Размер деревьев разбора Первый щаг на пути к лемме о накачке для КС-языков состоит в том, чтобы рассмотреть внд и размер деревьев разбора. Одно из применений НФХ вЂ” преобразовывать деревья разбора в бинарные (двоичные). Такие деревья имеют ряд удобных свойств, и одно вз ввх используется здесь. Теорема 7.17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
