dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 63
Текст из файла (страница 63)
7.1.5. Íîðìàëüíàÿ ôîðìà ÕîìñêîãîЗавершим изучение грамматических упрощений, показав, что для каждого непустогоКС-языка, не включающего ε, существует грамматика G, все продукции которой имеютодну из следующих двух форм.1.A → BC, где A, B и C — переменные.2.A → a, где A — переменная, a — терминал.Кроме того, G не имеет бесполезных символов. Такая форма грамматик называется нормальной формой Хомского, или НФХ, а грамматики в такой форме — НФХ-грамматиками.Для приведения грамматики к НФХ начнем с ее формы, удовлетворяющей теореме 7.14, т.е.
грамматика свободна от бесполезных символов, цепных и ε-продукций. Каждая продукция такой грамматики либо имеет вид A → a, допустимый НФХ, либо имееттело длиной не менее 2. Нужно выполнить следующие преобразования:а) устроить так, чтобы все тела длины 2 и более состояли только из переменных;б) разбить тела длины 3 и более на группу продукций, тело каждой из которыхсостоит из двух переменных.Конструкция для а следующая.
Для каждого терминала a, встречающегося в продукции длины 2 и более, создаем новую переменную, скажем, A. Эта переменная имеетединственную продукцию A → a. Используем переменную A вместо a везде в телах про280Стр. 280ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂдукций длины 2 и более. Теперь в теле каждой продукции либо одиночный терминал,либо как минимум две переменные и нет терминалов.Для шага б нужно разбить каждую продукцию вида A → B1B2…Bk, где k ≥ 3, на группу продукций с двумя переменными в каждом теле.
Введем k – 2 новых переменных C1,C2, …, Ck–2 и заменим исходную продукцию на k – 1 следующих продукций.A → B1C1, C1 → B2C2, …, Ck–3 → Bk–2Ck–2, Ck–2 → Bk–1BkПример 7.15. Приведем грамматику из примера 7.12 к НФХ. Для части а заметим,что у грамматики есть восемь терминалов, a, b, 0, 1, +, *, ( и ), каждый из которых встречается в теле, не являющемся одиночным терминалом. Таким образом, нужно ввести восемь новых переменных, соответствующих этим терминалам, и восемь следующих продукций, где переменная заменяется “своим” терминалом.A→aB→bZ→0O→1P→+M→*L→(R→)Введя эти продукции и заменив каждый терминал в теле, не являющемся одиночным терминалом, соответствующей переменной, получим грамматику, изображенную на рис.
7.2.E → EPT | TMF | LER | a | b | IA | IB | IZ | IOT → TMF | LER | a | b | IA | IB | IZ | IOF → LER | a | b | IA | IB | IZ | IOI → a | b | IA | IB | IZ | IOA→aB→bZ→0O→1P→+M→*L→(R→)Рис. 7.2. Преобразование тел к одиночным терминалам или нескольким переменнымТеперь все продукции находятся в НФХ, за исключением тех, тела которых имеютдлину 3: EPT, TMF, LER.
Некоторые из этих тел встречаются в нескольких продукциях,но каждое тело преобразуется один раз.Для тела EPT вводится новая переменная C1, и продукция E → EPT меняется наE → EC1 и C1 → PT. Для тела TMF вводится переменная C2. Две продукции с этим телом,E → TMF и T → TMF, меняются на E → TC2, T → TC2 и C2 → MF. Для LER вводится C3 итри продукции с этим телом, E → LER, T → LER и F → LER, меняются на E → LC3,T → LC3, F → LC3 и C3 → ER. Окончательная НФХ-грамматика показана на рис. 7.3.7.1. ÍÎÐÌÀËÜÍÛÅ ÔÎÐÌÛ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр.
281281E → EC1 | TC2 | LC3 | a | b | IA | IB | IZ | IOT → TC2 | LC3 | a | b | IA | IB | IZ | IOF → LC3 | a | b | IA | IB | IZ | IOI → a | b | IA | IB | IZ | IOA→aB→bZ→0O→1P→+M→*L→(R→)C1 → PTC2 → MFC3 → ERРис. 7.3. Преобразование тел к одиночным терминалам или двум переменнымТеорема 7.16. Если G — КС-грамматика, язык которой содержит хотя бы одну непустую цепочку, то существует НФХ-грамматика G1, причем L(G1) = L(G) – {ε}.Доказательство. По теореме 7.14 можно найти КС-грамматику G2, для которойL(G2) = L(G) – {ε}, причем G2 свободна от бесполезных символов, цепных и ε-продукций. Конструкция, преобразующая G2 в НФХ-грамматику G1, изменяет продукции такимобразом, что каждая продукция из G2 может быть проимитирована одной или несколькимипродукциями из G1. Наоборот, каждая из введенных в G1 переменных соответствует лишьодной продукции, поэтому эти переменные можно использовать только надлежащим образом. Более строго, докажем, что w ∈ L(G2) тогда и только тогда, когда w ∈ L(G1).(Необходимость) Если w порождается в G2, то легко заменить каждую использованную продукцию, скажем, A → X1X2…Xk, последовательностью продукций из G1.
Такимобразом, один шаг порождения в G2 превращается в один или несколько шагов в порождении w, использующем продукции G1. Во-первых, если Xi — терминал, то G1 имеет соответствующую переменную Bi и продукцию Bi → Xi. Во-вторых, если k > 2, то G1 имеетпродукции A → B1C1, C1 → B2C2 и так далее, где Bi есть либо переменная, введенная длятерминала Xi, либо сам Xi, если это переменная.
Эти продукции имитируют в G1 одиншаг порождения в G2, использующий продукцию A → X1X2…Xk. Делаем вывод, что в G1существует порождение w, поэтому w ∈ L(G1).(Достаточность) Предположим, что w ∈ L(G1). Тогда в G1 существует дерево разбора с отметкой корня S и кроной w. Преобразуем это дерево в дерево разбора в G2, такжеимеющее отметку корня S и крону w.282Стр. 282ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСначала “сделаем откат” части б построения НФХ. Предположим, существует узел сотметкой A и сыновьями, отмеченными B1 и C1, где C1 — одна из переменных, введенных вчасти б.
Тогда данная часть дерева разбора должна выглядеть, как на рис. 7.4, а. Посколькукаждая из этих введенных переменных соответствует лишь одной продукции, существуеттолько один способ для их возникновения, и все эти переменные, предназначенные для обработки продукции A → B1B2…Bk, должны появляться вместе (см. рис. 7.4, а).Каждый такой куст узлов в дереве разбора можно заменить продукцией, которую онипредставляют. Преобразование дерева разбора показано на рис. 7.4, б.Полученное дерево все еще не обязательно является деревом разбора в G2. Причина втом, что на шаге а построения НФХ были введены другие переменные, порождающие1122k-2k-1kа)12kб)Рис.
7.4. Дерево разбора должно использовать введенные переменныеспециальным образом7.1. ÍÎÐÌÀËÜÍÛÅ ÔÎÐÌÛ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 283283одиночные терминалы. Однако их можно обнаружить в полученном дереве разбора и заменить узел, отмеченный такой переменной A, и его единственного сына, отмеченного a,одиночным узлом с отметкой a. Теперь каждый внутренний узел дерева разбора образуетпродукцию G2, и мы приходим к выводу, что w ∈ L(G2). Íîðìàëüíàÿ ôîðìà ÃðåéáàõСуществует еще одна интересная нормальная форма для грамматик, которая не будетобоснована.
Любой непустой язык, не включающий ε, есть L(G) для некоторой грамматики G с продукциями вида A → aα, где a — терминал, а α — цепочка из нуля илинескольких переменных. Преобразование грамматики к этой форме является сложным, даже если задачу упростить, скажем, начав с НФХ-грамматики. Иначе говоря,первая переменная каждой продукции расширяется до тех пор, пока не будет получентерминал. Однако на этом пути возможны циклы, в которых терминал не достигается,и этот процесс необходимо “замкнуть”.
Для того чтобы породить все последовательности переменных, которые могут появиться на пути к порождению этого терминала,создается продукция с терминалом в качестве первого символа тела и переменнымивслед за ним.Эта форма, называемая нормальной формой Грейбах, по имени Шейлы Грейбах(Sheila Greibach), которая первой дала способ построения таких грамматик, имеет несколько интересных следствий. Поскольку каждое использование продукции вводитровно один терминал в выводимую цепочку, цепочка длины n порождается в точности за n шагов.
Кроме того, если применить конструкцию из теоремы 6.13 для построения МП-автомата по грамматике в нормальной форме Грейбах, то получаетсяМП-автомат без ε-переходов, показывающий, что такие переходы в МП-автоматевсегда можно удалить.7.1.6.
Óïðàæíåíèÿ ê ðàçäåëó 7.17.1.1.(∗) Найдите грамматику, не содержащую бесполезных символов и эквивалентную следующей грамматике.S → AB | CAA→aB → BC | ABC → aB | b7.1.2.Рассмотрите следующую грамматику:S → ASB | εA → aAS | aB → SbS | A | bbа) удалите ε-продукции;284Стр. 284ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂб) удалите цепные продукции;в) есть ли здесь бесполезные символы? Если да, удалите их;г) приведите грамматику к нормальной форме Хомского.7.1.3.Выполните упражнение 7.1.2 со следующей грамматикой.S → 0A0 | 1B1 | BBA→CB→S|AC→S|ε7.1.4.Выполните упражнение 7.1.2 со следующей грамматикой.S → AAA | BA → aA | BB→ε7.1.5.Выполните упражнение 7.1.2 со следующей грамматикой.S → aAa | bBb | εA→C|aB→C|bC → CDE | εD → A | B | ab7.1.6.Постройте НФХ-грамматику для множества цепочек сбалансированных скобок.Можно начать с грамматики, находящейся в НФХ.7.1.7.(!!) Пусть G — КС-грамматика с p продукциями и длины тел продукций не пре*восходят n.
Докажите, что если A ⇒ ε, то найдется порождение ε из A, в котоGром не более, чем (np – 1)/(n – 1) шагов. Как близко можно на самом деле подойти к этой границе?7.1.8.(!) Предположим, что нам дана грамматика G с n продукциями, ни одна из которых не является ε-продукцией, и мы преобразуем ее в НФХ:а) докажите, что НФХ-грамматика имеет не более, чем O(n2) продукций;б) докажите, что у НФХ-грамматики число продукций может быть прямо пропорциональным n2. Указание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
