Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Лемма о разрастании для КС-языков

Лемма о разрастании для КС-языков


Для КС-языков выполняется "лемма о разрастании", аналогичная лемме о разрастании для регулярных языков. Она формулирует необходимое условие того, что язык является контекстно-свободным.


Теорема 8.4 (лемма о разрастании для КС-языков). Для любого КС-языка [math]L[/math] существует натуральная константа [math]k[/math] (зависящая от [math]L[/math]), такая, что любая цепочка [math]x\in L[/math], длина которой [math]|z|>k[/math], представима в виде соединения пяти цепочек, [math]z=uxwyv[/math], где [math]|xy|>0,~ |xwy|\leqslant k[/math], и каждая цепочка [math]z_n=ux^nwy^nv,~n\geqslant0[/math], принадлежит [math]L[/math].


Так как [math]L[/math] — КС-язык, то существует КС-грамматика [math]G=(V,N,S,P)[/math], порождающая язык [math]L[/math], то есть [math]L=L(G)[/math].


Фиксируем произвольно нетерминал [math]A\in N[/math] и рассмотрим множество [math]\mathcal{D}(A)[/math] всех выводов, начинающихся с [math]A[/math], таких, что высота дерева вывода не превышает числа [math]|N|+1[/math] нетерминалов грамматики [math]G[/math], увеличенного на единицу. Множество [math]\mathcal{D}(A)[/math] конечно, так как высота дерева вывода, а следовательно, и его длина ограничены сверху (см. замечание 8.2). Таким образом, каждое множество [math]\mathcal{D}(A)[/math] при [math]A\in N[/math] есть конечное множество конечных выводов. Множество выводов [math]\mathcal{D}[/math] определим как объединение множеств [math]\mathcal{D}(A)[/math] по всем [math]A\in N[/math]. Ясно, что и это множество выводов конечно, так как конечно множество нетерминалов грамматики. Введем подмножество [math]\mathcal{A}[/math] всех таких цепочек в объединенном алфавите, что они являются последними цепочками выводов из [math]\mathcal{D}[/math]. Иначе говоря, [math]\mathcal{A}[/math] — это множество всех таких цепочек [math]\alpha[/math] в объединенном алфавите, что существует дерево вывода [math]\alpha[/math] (из некоторого нетерминала грамматики [math]G[/math]), высота которого не больше [math]|N|+1[/math]. В силу конечности множества [math]\mathcal{D}[/math] конечно и множество [math]\mathcal{A}[/math]. Тогда положим


[math]k=\max_{\alpha\in\mathcal{A}}|\alpha|,[/math]

т.е. введем константу [math]k[/math] как наибольшую длину среди всех цепочек множества [math]\mathcal{A}[/math].


Пусть теперь [math]z\in L[/math], причем [math]|z|>k[/math]. Тогда [math]S\vdash_{G}^{\ast}z[/math], и в силу определения константы [math]k[/math] любое дерево вывода цепочки z имеет высоту, большую [math]|N|+1[/math]. Фиксируем какое-нибудь дерево [math]T[/math] вывода цепочки [math]z[/math].


Выделим в дереве [math]T[/math] максимальное поддерево с корнем [math]R[/math], высота которого равна [math]|N|+1[/math] (рис. 8.25).


Максимальное поддерево с корнем

Тогда, согласно следствию 8.1, получим (для некоторых терминальных цепочек [math]u_1[/math] и [math]v_1[/math])


[math]S\vdash^{\ast}u_1Rv_1\vdash^{\ast}u_1z_1v_1,[/math]
(8.1)

где [math]z=u_1z_1v_1[/math], т.е. существует вывод цепочки [math]z_1=u_2xwyv_2[/math], являющейся подцепочкой цепочки z, из нетерминала [math]R[/math], такой, что высота дерева этого вывода равна [math]|N|+1[/math].


Напомним, что высота дерева есть максимальная длина пути в этом дереве из корня в лист. Так как длина пути в дереве вывода КС-грамматики равна числу замен нетерминалов в некотором фрагменте вывода, то при выводе цепочки [math]z_1[/math] из [math]R[/math] число замен нетерминалов строго больше числа всех нетерминалов грамматики [math]G[/math]. Это означает, что в выводе z\ из [math]R[/math] какой-то нетерминал [math]Q[/math] повторяется дважды (возможно, что [math]Q=R[/math]) и на некотором пути из вершины [math]R[/math] в один из листьев будут по крайней мере две разные вершины, помеченные одним и тем же нетерминалом [math]Q[/math]. Тогда рассмотрим два максимальных поддерева дерева [math]T[/math], корневые вершины которых являются указанными выше вершинами с меткой [math]Q[/math] (см. рис. 8.25). Выделению этих максимальных поддеревьев соответствует выделение фрагментов вывода [math]z_1[/math] из [math]R[/math], таких, что для некоторых терминальных цепочек [math]u_2,v_2,x,y,w[/math] выполняется выводимость, где [math]z_1=u_2xwyv_2[/math]


[math]R\vdash^{\ast} u_2Qv_2\vdash^{\ast} u_2xQyv_2\vdash^{\ast} u_2xwyv_2,[/math]
(8.2)

Соотношения (8.2) показывают, что имеют место выводимости


[math]Q\vdash^{\ast} xQy,[/math]
(8.3)

[math]Q\vdash^{\ast} w.[/math]
(8.4)

Это значит, что существует дерево вывода цепочки [math]xwy[/math] из нетерминала [math]Q[/math] ("большое" дерево с корневой вершиной [math]Q[/math] на рис. 8.25) и в нем — максимальное поддерево с корневой вершиной, помеченной тем же символом [math]Q[/math], являющееся деревом вывода цепочки [math]w[/math] из [math]Q[/math] ("маленькое" дерево с корневой вершиной [math]Q[/math] на рис. 8.25). При этом, так как "большое" дерево с корневой вершиной [math]Q[/math] является поддеревом дерева с корневой вершиной [math]R[/math] высотой [math]|N|+1[/math], то его высота будет не больше чем [math]|N|+1[/math], откуда в силу выбора константы [math]k[/math] имеем [math]|xwy|\leqslant k[/math].


Объединяя (8.1) и (8.2), получим такое представление вывода цепочки [math]z[/math] из аксиомы [math]S\colon[/math]


[math]S\vdash^{\ast} u_1R_1v_1\vdash^{\ast} u_1u_2Qv_2v_1 \underbrace{\vdash^{\ast} u_1u_2xQyv_2v_1}\vdash^{\ast} u_1u_2xwyv_2v_1.[/math]
(8.5)

Полагая [math]u=u_1u_2[/math] и [math]v=v_2v_1[/math], получим [math]z=uxwyv[/math], и тем самым мы доказали представление цепочки [math]z[/math] в виде соединения определенных пяти цепочек.


Из (8.5) следует, что, получив (при выводе [math]z[/math] из [math]S[/math]) цепочку [math]u_1u_2Qv_2v_1[/math], можно с учетом (8.4) сразу из нетерминала [math]Q[/math] вывести цепочку [math]w[/math], и тогда


[math]S\vdash^{\ast} u_1Rv_1\vdash^{\ast} u_1u_2Qv_2v_1\vdash^{\ast} u_1u_2wv_2v_1=uwy[/math]
(8.6)

(в выводе (8.5) выбрасываем последовательность шагов над фигурной скобкой).

В то же время вывод (8.5) можно с учетом (8.3) модифицировать так, что после получения цепочки [math]u_1u_2Qv_2v_2=uQv[/math] многократно (не менее одного раза) повторять вывод цепочки [math]xQy[/math] из [math]Q\colon[/math]


[math]\begin{aligned} S\vdash^{\ast} u_1Rv_1\vdash^{\ast} u_1u_2Qv_2v_1&\vdash^{\ast} uQv\vdash^{\ast} uxQyv\vdash^{\ast} uxxQyyv\vdash^{\ast}\ldots\vdash^{\ast}\\ &\vdash^{\ast} ux^n Qy^nv\vdash^{\ast} ux^nwy^nv\end{aligned}[/math]
(8.7)

(в выводе (8.5) последовательность шагов над фигурной скобкой повторяем [math]n[/math] раз).

Итак, в силу (8.6) цепочка [math]z_0=uwv\in L[/math], а в силу (8.7) и цепочка [math]z_n= ux^nwy^nv[/math] для любого [math]n>0[/math] принадлежит языку [math]L[/math]. Тем самым мы доказали, что [math](\forall n\geqslant0)(ux^nwy^nv\in L)[/math].


Осталось доказать, что длина цепочки [math]xy[/math] не меньше 1 (или, что равносильно, цепочки [math]x[/math] и [math]y[/math] не являются одновременно пустыми).


Согласно теореме 8.2, можно считать без ограничения общности, что в множестве правил вывода грамматики [math]G[/math] нет ни λ-правил (кроме, быть может, правила [math]S\to \lambda[/math]), ни цепных правил. Кроме того, в силу замечания 8.6 можно считать, что правило [math]S\to\lambda[/math] применяется только при выводе пустой цепочки, а поскольку высота дерева цепочки [math]z[/math] строго больше 1, то [math]z\ne\lambda[/math] и правило [math]S\to \lambda[/math] не применяется при выводе [math]z[/math] из аксиомы [math]S[/math].


Тогда, предполагая, что [math]x=y=\lambda[/math], получим [math]Q\vdash^{\ast}Q[/math], а это возможно лишь при условии применения в соответствующем выводе цепных правил или правил с пустой правой частый, что ввиду сказанного выше не может иметь места. Итак, цепочка [math]xy[/math] не пуста, т.е. [math]|xy|>0[/math], что и завершает доказательство теоремы.


Следствие 8.2. В любом бесконечном КС-языке существует последовательность слов, длины которых образуют возрастающую арифметическую прогрессию.


Пусть КС-язык [math]L[/math] бесконечен. Тогда в нем нет цепочки наибольшей длины. Следовательно, найдется цепочка [math]z\in L[/math], длина которой больше константы [math]k[/math], определяемой леммой о разрастании. Согласно этой лемме, цепочка [math]z[/math] может быть представлена в виде [math]z=uxwyv[/math] для некоторых цепочек [math]u,x,w,y,v[/math], таких, что [math]|xwy|\leqslant k,~|xy|>0[/math]. Тогда последовательность [math]z_n=\{ux^nwy^nv\}_{n\geqslant0}[/math] является искомой, так как длины ее цепочек образуют возрастающую арифметическую прогрессию со знаменателем [math]|xy|[/math].


Замечание 8.7. Любой конечный язык [math]\{u_1,\ldots,u_m\}[/math] (в каком-то алфавите [math]V[/math]) порождается КС-грамматикой с множеством правил [math]S\to u_1\mid\ldots\mid u_m[/math]. Дерево вывода любой цепочки в этой грамматике имеет высоту, не большую 1 (высоту 0 имеет дерево вывода нулевой длины аксиомы [math]S[/math] из себя самой, а каждая терминальная цепочка, т.е. цепочка [math]u_i,~i=\overline{1,m}[/math], имеет дерево вывода высоты 1). Следовательно, в данном случае константа [math]k[/math] равна наибольшей длине цепочки [math]u_i[/math] и цепочки, длина которой была бы больше [math]k[/math], не существует.


Таким образом, для конечного языка утверждение леммы о разрастании тривиально выполняется, а именно, не существует цепочек, длины которых превосходят константу [math]k[/math].




Пример 8.11. а. Язык [math]\{a^{n^2}\colon\,n\geqslant0\}[/math] не является контекстно-свободным, поскольку из длин принадлежащих ему слов нельзя образовать арифметическую прогрессию: [math](n+1)^2-n^2=2n+1[/math].


б. Язык {[math]a^s\colon\,s[/math] — простое число} не является КС-языком по той же причине.


в. Рассмотрим язык [math]\{a^nb^nc^n\mid n\geqslant0\}[/math]. Длины его слов образуют арифметическую прогрессию, но тем не менее этот язык не является контекстно-свободным. Действительно, предположим противное. Тогда для любого достаточно большого [math]n[/math] слово [math]a^nb^nc^n[/math] можно представить в виде [math]uxwyv[/math]. Проанализируем, как могут располагаться в слове цепочки [math]x,\,w[/math] и [math]y[/math]. Поскольку условие леммы о разрастании должно выполняться для всех достаточно длинных слов языка, т.е. слов, длина которых строго больше константы [math]k[/math] из леммы, то в целях проверки невыполнения условия можно брать слова/длина которых заведомо превышает указанную константу*. Для анализируемого в этой задаче языка примем, что [math]n>k[/math]. Тогда возможны следующие случаи:


1) [math]xwy=\alpha^l[/math], где [math]l\leqslant k<n[/math], а [math]\alpha[/math] обозначает одну из букв [math]a,b,c[/math] (т.е. цепочка [math]xwy[/math] целиком расположена или в "зоне" символов [math]a[/math], или в "зоне" символов [math]b[/math], или в "зоне" символов [math]c[/math]);


2) [math]xwy=a^lb^m[/math] или [math]xwy=b^lc^m[/math], где [math]l+m\leqslant k<n[/math] и [math]l,m>0[/math] (т.е. цепочка [math]xwy[/math] расположена "на стыках зон" различных символов и содержит ненулевое число символов каждой из "зон"). В силу выбора числа [math]n[/math] никакие другие способы расположения подцепочки [math]xwy[/math] в цепочке [math]a^nb^nc^n[/math] невозможны (отсюда следует, что подходящий выбор числа [math]n[/math] позволил нам уменьшить число вариантов расположения подцепочки [math]xwy[/math] в цепочке языка).


*Предполагая, что язык является контекстно-свободным, мы тем самым в силу леммы о разрастании предполагаем, что оказывается фиксированной какая-то константа [math]k[/math], о которой идет речь в условии леммы. Мы не можем знать значения этой константы, но это нам и не нужно: достаточно знать, что вследствие нашего предположения константа [math]k[/math] как-то фиксирована, и мы можем быть уверены в том, что в бесконечном КС-языке найдутся цепочки, длины которых превысят [math]k[/math].


Теперь если мы станем повторять ("накачивать") цепочки [math]x[/math] и [math]y[/math] в первом случае, то начнет расти число одного из символов [math]a,\,b[/math] или [math]c[/math], тогда кале число остальных двух символов будет оставаться прежним, и получаемые при этом цепочки уже не будут принадлежать заданному языку. Во втором же случае при "наг качке" возникнут цепочки, содержащие вхождение цепочки [math]bd[/math] или [math]cb[/math], что также недопустимо (символы [math]a,b,c[/math] начнут "перемешиваться"). Получается, что мы не можем представить любую достаточно длинную цепочку [math]a^nb^nc^n[/math] в виде [math]uxwyv[/math] так, чтобы при этом выполнялось условие леммы о разрастании. Следовательно, исходный язык не является контекстно-свободным.




В целом техника доказательства с помощью леммы о разрастании для КС-языков "отрицательных" утверждений типа "данный язык не является контекстно-свободным" аналогична технике доказательства утверждений о нерегулярности языков с использованием леммы о разрастании для регулярных языков.


Обратим внимание на различие структур "накачиваемых" цепочек в регулярных и контекстно-свободных языках.


Лемма о разрастании для регулярных языков утверждает, что любая достаточно длинная цепочка регулярного языка представима как соединение трех подцепочек, из которых средняя подцепочка ограничена сверху по длине и не пуста, ее можно "накачивать", повторяя любое число раз, в том числе и ни разу, т.е. можно выбросить вообще, и такая "накачка" не выводит за пределы данного языка (рис. 8.26).


Лемма о разрастании для регулярных языков

Лемма о разрастании для КС-языков утверждает в аналогичной ситуации, что цепочка языка представима как соединение пяти подцепочек, причем если рассмотреть три средние подцепочки, то "накачиваются" края — первая и третья из них, а самая середина не меняется (рис. 8.27).


Лемма о разрастании для КС-языков

Обратим внимание на то, что ограничение сверху длины подцепочки [math]xwy[/math] константой [math]k[/math], вытекающее из леммы о разрастании, очень важно и, не используя его, вообще говоря, нельзя доказать, что данный язык не является контекстно-свободным. Рассмотрим в этой связи такой пример.




Пример 8.12. Пусть язык [math]L[/math] определен как множество всех цепочек в алфавите [math]\{a,b\}[/math] вида [math]a^nb^ma^nb^m,~n\geqslant0[/math]. Докажем, что он не является контекстно-свободным.


Предполагая, что [math]L[/math] — КС-язык, получим, что для достаточно больших [math]n[/math] и [math]m[/math] цепочка [math]a^nb^ma^nb^m[/math] допускает представление в виде [math]uxwyv[/math]. Выберем числа [math]n[/math] и [math]m[/math] так, что они больше, чем определенная леммой о разрастании константа [math]k[/math] для языка [math]L[/math]. Анализируем варианты "размещения" подцепочки [math]xwy[/math] в цепочке [math]a^nb^na^nb^m[/math]: очевидно, что "накачка" невозможна, если цепочки [math]x[/math] и [math]y[/math] обе целиком находятся в "зоне" какого-то одного символа, [math]a[/math] или [math]b[/math]; если же, скажем, [math]x=a^pb^s[/math] при [math]p,s\ne0[/math], т.е. цепочка [math]x[/math] находится "на стыке зон" символов [math]a[/math] и [math]b[/math], то при "накачке" возникнет более чем одно вхождение подцепочки [math]ba[/math] в цепочку языка [math]L[/math], что противоречит определению этого языка; если же [math]x=b^pa^s[/math] при [math]p,s\ne0[/math], то при "накачке" возникнет более двух вхождений подцепочки [math]ab[/math], что также невозможно. Аналогично анализируется размещение цепочки [math]y[/math] "на стыках зон". В силу того что [math]n,m>k[/math], a [math]|xwy|\leqslant k[/math], никакие другие варианты расположения подцепочки [math]xwy[/math] невозможны.


Если ограничение на длину этой подцепочки опустить, то окажется возможным такое ее вхождение в цепочку [math]a^mb^na^mb^n[/math], что [math]x=a^s,~w=a^pb^ma^q[/math] и [math]y=a^r[/math] для некоторых положительных [math]s,p,q,r[/math]. Тогда при [math]s=r[/math] (чего априори нельзя отвергать, так как условия леммы о разрастании не требуют, чтобы длины цепочек [math]x[/math] и [math]y[/math] были обязательно различными) "накачка" цепочек [math]x[/math] и [math]y[/math] дала бы "синхронное" увеличение числа символов [math]a[/math] при неизменном числе символов [math]b[/math], что не вывело бы нас за пределы языка [math]L[/math]. Таким образом, нам тогда не удалось бы доказать, что определяемое леммой о разрастании представление цепочки [math]a^mb^na^mb^n[/math] не может иметь места.




Рассмотрим еще один пример, важный для понимания леммы о разрастании и ее применений.


Пример 8.13. Зададим язык [math]L'=\{a^nb^nc^p\colon\, n,p\geqslant0,~p\geqslant n\}[/math]. Здесь при размещении "накачиваемых" цепочек в "зоне" символов [math]c[/math] "накачка" не выводит за пределы языка [math]L'[/math] (так как в его цепочках число символов [math]c[/math] может на сколько угодно превышать число символов [math]a[/math] и [math]b[/math]). Тем не менее и в этом случае условие леммы о разрастании не выполняется.


Действительно, для достаточно большого [math]n[/math] возьмем цепочку [math]a^nb^nc^n\in L'[/math] (т.е. цепочку языка [math]L'[/math] при [math]n=p[/math]). Если в представлении такой цепочки в виде [math]a^nb^nc^n=uxwyv[/math] (согласно лемме о разрастании) цепочка [math]xwy=c^l[/math] при [math]0<l\leqslant n[/math] (т.е. "накачиваемые" цепочки располагаются целиком в "зоне" символов [math]c[/math]), то цепочка [math]uwv=a^nb^nc^{n-|xy|}\notin L'[/math], так как [math]|xy|\geqslant1[/math] и [math]n-|xy|<n[/math], т.е. число символов с окажется меньше, чем число символов [math]a[/math] и [math]b[/math]. Таким образом, несмотря на то что "накачка" цепочек [math]x,y[/math] в данном случае возможна, нельзя их выбросить, оставаясь в пределах языка. Невозможность других вариантов расположения подцепочки [math]xwy[/math] в цепочке языка [math]L'[/math] доказывается точно так же, как и в предыдущих примерах.




Итак, нужно помнить, что выполнение условий леммы о разрастании предполагает и возможность выбрасывания "накачиваемых" цепочек — все цепочки [math]z_n=ux^nwy^nv[/math] из условия леммы при [math]n\geqslant0[/math] должны оставаться в языке [math]L[/math], и если условие леммы выполняется при всех положительных [math]n[/math], но не выполняется при [math]n=0[/math], то этого достаточно для признания того, что цепочка [math]z=uxwyv\in L[/math] не удовлетворяет условию леммы о разрастании.


Аналогичная ситуация имеет место, конечно, и при использовании леммы о разрастании для регулярных языков.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved