dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 62
Текст из файла (страница 62)
Докажем индукцией по длине n порождения,G*что A ⇒ w.G17.1. ÍÎÐÌÀËÜÍÛÅ ÔÎÐÌÛ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 275275Базис. Один шаг. A → w является продукцией в G. Поскольку w ≠ ε, эта же продукция*есть и в G1, поэтому A ⇒ w.G1Индукция.Пустьв порожденииnшагов,n > 1.Тогдаоно**GGимеетвидA ⇒ Y1Y2…Ym ⇒ w. Цепочку w можно разбить на w1w2…wk так, что Yi ⇒ wi для i = 1, 2,G…, m. Пусть X1, X2, …, Xk будут теми из Yj (в порядке записи), для которых wi ≠ ε. k ≥ 1,поскольку w ≠ ε. Таким образом, A → X1X2…Xk является продукцией в G1.*Утверждаем, что X1X2…Xk ⇒ w, поскольку только Yj, которых нет среди X1, X2, …, Xk,Gиспользованы для порождения ε и не вносят ничего в порождение w. Так как каждое из по*рождений Yj ⇒ wj содержит менее n шагов, к ним можно применить предположение инG**дукции и заключить, что если wj ≠ ε, то Yj ⇒ wj.
Таким образом, A ⇒ X1X2…Xk ⇒ w.G1G1G1Завершим доказательство. Нам известно, что w ∈ L(G1) тогда и только тогда, когда*S ⇒ w. Полагая, что A = S в описанных выше рассуждениях, получаем, что w ∈ L(G1) тоG1*гда и только тогда, когда S ⇒ w и w ≠ ε. Таким образом, w ∈ L(G1) тогда и только тогда,Gкогда w ∈ L(G1) и w ≠ ε.
7.1.4. Óäàëåíèå öåïíûõ ïðîäóêöèéЦепная продукция — это продукция вида A → B, где и A, и B являются переменными.Эти продукции могут быть полезными: в примере 5.27 мы видели, как использованиецепных продукций E → T и T → F позволило построить следующую однозначную грамматику для простых арифметических выражений.I→a | b | Ia | Ib | I0 | I1F→I | (E)T→F|T*FE→T|E+TВместе с тем, цепные продукции могут усложнять некоторые доказательства и создавать излишние шаги в порождениях, которые по техническим соображениям там совсемне нужны. Например, в продукции E → T переменную T можно расширить обоими возможными способами, заменив эту продукцию двумя: E → F | T * F.
Это изменение всееще не избавляет от цепных продукций из-за появления E → F. Дальнейшая замена F дает E → I | (E) | T * F, однако при этом остается E → I. Но если в этой продукции заменитьI всеми шестью возможными способами, то получим следующие продукции.276Стр. 276ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂE → a | b | Ia | Ib | I0 | I1 | (E) | T * FКак видно, цепных продукций для E нет.
Заметим, что продукция E → a не являетсяцепной, единственный символ в ее теле — терминал, а не переменная.Представленная выше техника расширения цепных продукций до их исчезновенияработает довольно часто. Однако она терпит неудачу, если в грамматике есть цикл изцепных продукций, вроде A → B, B → C и C → A. Техника, гарантирующая результат,*включает первоначальное нахождение всех пар переменных A и B, для которых A ⇒ Bполучается с использованием последовательности лишь цепных продукций.
Заметим, что*A ⇒ B возможно и без использования цепных продукций, например, с помощью продукций A → BC и C → ε.Определив все подобные пары, любую последовательность шагов порождения, в которой A ⇒ B1 ⇒ B2 ⇒ … ⇒ Bn ⇒ α с нецепной продукцией Bn → α, можно заменитьпродукцией A → α. Однако вначале рассмотрим индуктивное построение пар (A, B), для*которых A ⇒ B получается с использованием лишь цепных продукций. Назовем такуюпару цепной парой (unit pair).*Базис.
(A, A) является цепной парой для любой переменной, т.е. A ⇒ A за нульшагов.Индукция. Предположим, что пара (A, B) определена как цепная, и B → C — продукция с переменной C. Тогда (A, C) — цепная пара.Пример 7.10. Рассмотрим грамматику выражений из примера 5.27, воспроизведенную выше. Базис дает цепные пары (E, E), (T, T), (F, F) и (I, I). На индуктивном шагеможно сделать следующие порождения пар.1.(E, E) и продукция E → T дают пару (E, T).2.(E, T) и продукция T → F — пару (E, F).3.(E, F) и F → I дают пару (E, I).4.(T, T) и T → F — пару (E, I).5.(T, F) и F → I — пару (T, I).6.(F, F) и F → I — пару (F, I).Больше пар, которые можно было бы вывести, нет.
На самом деле эти десять пар представляют все порождения, использующие только цепные продукции. Способ построения пар теперь очевиден. Нетрудно доказать, что предложенный алгоритм обеспечивает порождение всех нужных пар. Зная эти пары, можно удалитьцепные продукции из грамматики и показать эквивалентность исходной и полученнойграмматик.7.1. ÍÎÐÌÀËÜÍÛÅ ÔÎÐÌÛ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 277277Теорема 7.11.
Приведенный выше алгоритм находит все цепные пары грамматики G,и только их.Доказательство. С помощью индукции по порядку обнаружения пар нетрудно пока*зать, что если пара (A, B) обнаружена, то A ⇒ B получается с использованием лишьGцепных продукций. Это оставляется в качестве упражнения.*Предположим, что A ⇒ B получено с использованием лишь цепных продукций. ПоGкажем с помощью индукции по длине порождения, что пара (A, B) будет обнаружена.Базис. Нуль шагов. Тогда A = B, и пара (A, B) обнаруживается согласно базису.*Индукция.
Предположим, что A ⇒ B получено за n шагов, n > 0, и на каждом из нихG*применялась цепная продукция. Тогда порождение имеет вид A ⇒ C ⇒ B. ПорождениеG*A ⇒ C состоит из n – 1 шагов, и по предположению индукции пара (A, C) обнаруживаGется. Наконец, используем индуктивную часть алгоритма, чтобы по паре (A, C) и продукции C → B обеспечить обнаружение пары (A, B). Для удаления цепных продукций по КС-грамматике G = (V, T, P, S) построим КСграмматику G1 = (V1, T, P1, S) следующим образом.1.Найдем все цепные пары грамматики G.2.Для каждой пары (A, B) добавим к P1 все продукции A → α, где B → α — нецепнаяпродукция из P.
Заметим, что при A = B все нецепные продукции для B из P простодобавляются к P1.Пример 7.12. Продолжим пример 7.10, где был выполнен шаг 1 описанного построениядля грамматики выражений из примера 5.27. На рис. 7.1 представлен шаг 2 алгоритма, строящий новое множество продукций. При этом первый член пары становится головой продукций, а в качестве их тел используются все тела нецепных продукций для второго члена.На заключительном шаге из грамматики (см. рис. 7.1) удаляются все цепные продукции. В итоге получается следующая грамматика без цепных продукций, которая порождает то же самое множество выражений, что и грамматика, изображенная на рис. 5.19.E → E + T | T * F | (E) | a | b | Ia | Ib | I0 | I1T → T * F | (E) | a | b | Ia | Ib | I0 | I1F → (E) | a | b | Ia | Ib | I0 | I1I → a | b | Ia | Ib | I0 | I1Теорема 7.13.
Если грамматика G1 построена по грамматике G с помощью алгоритмаудаления цепных продукций, описанного выше, то L(G1) = L(G).278Стр. 278ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂПараПродукции(E, E)E→E+T(E, T)E→T*F(E, F)E → (E)(E, I)E → a | b | Ia | Ib | I0 | I1(T, T)T→T*F(T, F)T → (E)(T, I)T → a | b | Ia | Ib | I0 | I1(F, F)F → (E)(F, I)F → a | b | Ia | Ib | I0 | I1(I, I)I → a | b | Ia | Ib | I0 | I1Рис.
7.1. Грамматика, построенная на шаге 2 алгоритма удаления цепных продукцийДоказательство. Докажем, что w ∈ L(G1) тогда и только тогда, когда w ∈ L(G).*(Достаточность) Предположим, S ⇒ w. Поскольку каждая продукция грамматикиG1G1 эквивалентна последовательности из нуля или нескольких цепных продукций G, за*которой следует нецепная продукция G, из α ⇒ β следует α ⇒ β. Таким образом, кажG1Gдый шаг порождения в G1 может быть заменен одним или несколькими шагами в G. Со*брав эти последовательности шагов вместе, получим, что S ⇒ w.G(Необходимость) Предположим, что w ∈ L(G). Тогда в соответствии с эквивалент*ностями из раздела 5.2 цепочка w имеет левое порождение, т.е.
S ⇒ w. Где бы в левомlmпорождении ни использовалась цепная продукция, переменная ее тела становитсякрайней слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в G можно разбить на последовательность “шагов”, в которых нуль или несколько цепных продукций сопровождаются нецепной. Заметим, что любая нецепнаяпродукция, перед которой нет цепных, сама по себе образует такой “шаг”. Но по построению грамматики G1 каждый из этих шагов может быть выполнен одной ее про*дукцией.
Таким образом, S ⇒ w. G1Подведем итог различным упрощениям грамматик, описанным выше. Нам желательно преобразовывать любую КС-грамматику в эквивалентную, которая не имеет беспо-7.1. ÍÎÐÌÀËÜÍÛÅ ÔÎÐÌÛ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 279279лезных символов, ε-продукций и цепных продукций. При этом немаловажен порядокприменения преобразований. Безопасным является следующий.1.Удалить ε-продукции.2.Удалить цепные продукции.3.Удалить бесполезные символы.Заметим, что подобно тому, как в разделе 7.1.1 результат удаления бесполезных символов зависел от порядка соответствующих шагов, данные три шага должны быть упорядочены именно так, иначе в грамматике могут остаться удаляемые элементы.Теорема 7.14. Если G — КС-грамматика, порождающая язык, в котором есть хотя быодна непустая цепочка, то существует другая грамматика G1, не имеющая бесполезныхсимволов, ε-продукций и цепных продукций, у которой L(G1) = L(G) – {ε}.Доказательство.
Начнем с удаления ε-продукций методом, описанным в разделе 7.1.3. Если затем удалить цепные продукции (см. раздел 7.1.4), то ε-продукции не появятся, поскольку каждое из тел новых продукций совпадает с некоторым телом одной изстарых. Наконец, удалим бесполезные символы методом раздела 7.1.1. Поскольку этопреобразование только удаляет продукции и символы, не вводя новых, то получаемаяграмматика будет по-прежнему свободна от цепных и ε-продукций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
