dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 64
Текст из файла (страница 64)
Рассмотрите конструкцию удаления цепныхпродукций.7.1.9.Дайте индуктивные доказательства, необходимые для завершения следующихтеорем:а) часть теоремы 7.4, в которой доказывалось, что обнаруживаемые символыдействительно являются порождающими;7.1. ÍÎÐÌÀËÜÍÛÅ ÔÎÐÌÛ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 285285б) теорема 7.6 в обе стороны, где доказывалась корректность алгоритма из раздела 7.1.2 для обнаружения достижимых символов;в) часть теоремы 7.11, где доказывалось, что все обнаруженные пары действительно являются цепными парами.7.1.10. (∗!) Можно ли для каждого КС-языка найти грамматику, все продукции которойимеют вид или A → BCD (тело состоит из трех переменных), или A → a (телообразовано одиночным терминалом)? Приведите либо доказательство, либоконтрпример.7.1.11.
В этом упражнении показывается, что для каждого КС-языка L, содержащегохотя бы одну непустую цепочку, найдется КС-грамматика в нормальной формеГрейбах, порождающая L – {ε}. Напомним, что тела продукций грамматики внормальной форме Грейбах (НФГ) начинаются терминалом. В построении используется ряд лемм и конструкций.1.Пусть КС-грамматика G имеет продукцию A → αBβ, и всеми продукциямидля B являются B → γ1 | γ2 | … | γn. Заменив A → αBβ всеми продукциями, укоторых вместо B подставлены тела всех B-продукций, получим A → αγ1β |αγ2β | … | αγnβ.
Построенная грамматика порождает тот же язык, что и G.Далее будем предполагать, что грамматика G для L находится в нормальнойформе Хомского, а ее переменные обозначены A1, A2, …, Ak.2.(∗!) Докажите, что путем повторных применений преобразования из части 1грамматику G можно превратить в эквивалентную грамматику, у которойтело каждой продукции для Ai начинается или терминалом, или Aj для некоторого j ≥ i.
В обоих случаях все символы после первого в теле продукции —переменные.3.(!) Пусть G1 — грамматика, полученная из G путем выполнения шага 2.Пусть Ai — произвольная переменная и Ai → Aiα1 | … | Aiαm — все Aiпродукции, тело которых начинается с Ai. Пусть Ai → β1 | … | βp — все остальные Ai-продукции. Заметим, что каждое βi начинается либо терминалом,либо переменной с индексом больше i. Введем новую переменную Bi и заменим первую группу из m продукций следующими:Ai → β 1 | … | β pBi → α1Bi | α1 | … | αmBi | αmДокажите, что полученная грамматика порождает тот же язык, что и G или G1.4.286Стр. 286(∗!) Пусть после шага 3 получена грамматика G2. Отметим, что тела всех Aiпродукций начинаются или терминалом, или Aj с j > i. Кроме того, тела Biпродукций начинаются или терминалом, или некоторым Aj. Докажите, чтоG2 имеет эквивалентную грамматику в НФГ.
Указание. Сначала преобразуйÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂте должным образом продукции для Ak, затем для Ak–1 и так далее до A1, используя часть 1. Затем снова с помощью части 1 преобразуйте продукциидля Bi в любом порядке.7.1.12. Используйте построения из упражнения 7.1.11 для преобразования в НФГ следующей грамматики.S → AA | 0A → SS | 17.2.
Ëåììà î íàêà÷êå äëÿ êîíòåêñòíî-ñâîáîäíûõ ÿçûêîâВ этом разделе развивается инструмент доказательства, что некоторые языки не являются контекстно-свободными. Теорема, называемая “леммой о накачке для контекстно-свободных языков”1, гласит, что в любой достаточно длинной цепочке КС-языкаможно найти две близлежащие короткие подцепочки (одна из них может быть пустой) исовместно их “накачивать”. Таким образом, обе подцепочки можно повторить i раз длялюбого целого i, и полученная цепочка также будет принадлежать языку.Эта теорема отличается от аналогичной для регулярных языков (теорема 4.1), гласящей, что всегда можно найти одну короткую цепочку для ее накачки. Разница видна, если рассмотреть язык типа L = {0n1n | n ≥ 1}.
Можно показать, что он нерегулярен, еслизафиксировать n и накачать подцепочку из нулей, получив цепочку, в которой символов0 больше, чем 1. Однако лемма о накачке для КС-языков утверждает, что можно найтидве короткие цепочки, поэтому нам пришлось бы использовать для накачки цепочку изнулей и цепочку из единиц, порождая таким образом только цепочки из L. Этот результат нас устраивает, так как L — КС-язык, а для построения цепочек, не принадлежащихязыку L, лемма о накачке для КС-языков использоваться и не должна.7.2.1. Ðàçìåð äåðåâüåâ ðàçáîðàПервый шаг на пути к лемме о накачке для КС-языков состоит в том, чтобы рассмотреть вид и размер деревьев разбора.
Одно из применений НФХ — преобразовывать деревья разбора в бинарные (двоичные). Такие деревья имеют ряд удобных свойств, и одноиз них используется здесь.Теорема 7.17. Пусть дано дерево разбора, соответствующее НФХ-грамматикеG = (V, T, P, S), и пусть кроной дерева является терминальная цепочка w. Если n — наибольшая длина пути (от корня к листьям), то |w| ≤ 2n–1.Доказательство. Докажем с помощью простой индукции по n.1Напомним, что в русскоязычной литературе был принят термин “лемма о разрастании”, но“накачка”, на наш взгляд, точнее отражает суть происходящего. — Прим. ред.7.2.
ËÅÌÌÀ Î ÍÀÊÀ×ÊÅ ÄËß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр. 287287Базис. n = 1. Напомним, что длина пути есть число ребер, т.е. на 1 меньше числаузлов. Таким образом, дерево с максимальной длиной пути 1 состоит из корня и листа,отмеченного терминалом. Цепочка w является этим терминалом, и |w| = 1. Поскольку2n–1 = 20 = 1, базис доказан.Индукция. Предположим, самый длинный путь имеет длину n, и n > 1. Корень дерева использует продукцию, которая должна иметь вид A → BC, поскольку n > 1, т.е.нельзя начать дерево, использовав продукцию с терминалом. Ни один из путей в поддеревьях с корнями в B и C не может иметь длину больше, чем n – 1, так как в этих путях исключено ребро от корня к сыну, отмеченному B или C.
Таким образом, по предположению индукции эти два поддерева имеют кроны длины не более 2n–2. Крона всего дерева представляет собой конкатенацию этих двух крон, поэтому имеет длину неболее 2n–2 + 2n–2 = 2n–2. Шаг индукции доказан. 7.2.2. Óòâåðæäåíèå ëåììû î íàêà÷êåЛемма о накачке для КС-языков подобна лемме о накачке для регулярных языков, нокаждая цепочка z КС-языка L разбивается на пять частей, и совместно накачиваются вторая и четвертая из них.Теорема 7.18. (Лемма о накачке для КС-языков.) Пусть L — КС-язык. Тогда существует такая константа n, что если z — произвольная цепочка из L, длина которой неменьше n, то можно записать z = uvwxy, причем выполняются следующие условия.1.|vwx| ≤ n.
Таким образом, средняя часть не слишком длинная.2.vx ≠ ε. Поскольку v и x — подцепочки, которые должны “накачиваться”, это условиегласит, что хотя бы одна из них непуста.3.uviwxiy ∈ L для всех i ≥ 0. Две цепочки, v и x, могут быть “накачаны” произвольноечисло раз, включая 0, и полученная при этом цепочка также будет принадлежать L.Доказательство. Вначале для L найдем грамматику G в нормальной форме Хомского. Технически это невозможно, если L есть КС-язык ∅ или {ε}. Однако при L = ∅ утверждение теоремы, которое говорит о цепочке z, не может быть нарушено, посколькутакой цепочки z нет в ∅. НФХ-грамматика G в действительности порождает L – {ε}, ноэто также не имеет значения, поскольку выбирается n > 0, и z никак не сможет быть ε.Итак, пусть НФХ-грамматика G = (V, T, P, S) имеет m переменных и порождает языкL(G) = L – {ε}. Выберем n = 2m.
Предположим, что z из L имеет длину не менее n. Потеореме 7.17 любое дерево разбора, наибольшая длина путей в котором не превышает m,должно иметь крону длиной не более 2m–1 = n/2. Такое дерево разбора не может иметькрону z, так как z для этого слишком длинная. Таким образом, любое дерево разбора скроной z имеет путь длиной не менее m + 1.288Стр. 288ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂНа рис. 7.5 представлен самый длинный путь в дереве для z, где k не менее m, и путьимеет длину k + 1. Поскольку k ≥ m, на этом пути встречается не менее m + 1 переменныхA0, A1, …, Ak.
Но V содержит всего m различных переменных, поэтому хотя бы две изm + 1 последних переменных на пути (т.е. от Ak–m до Ak включительно) должны совпадать. Пусть Ai = Aj, где k – m ≤ i ≤ j ≤ k.Тогда дерево можно разделить так, как показано на рис.
7.6. Цепочка w является кроной поддерева с корнем Aj. Цепочки v и x — это цепочки соответственно слева и справаот w в кроне большего поддерева с корнем Ai. Заметим, что цепных продукций нет, поэтому v и x не могут одновременно быть ε, хотя одна из них и может. Наконец, u и y образуют части z, лежащие соответственно слева и справа от поддерева с корнем Ai.012kРис. 7.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
