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

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

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

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


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

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


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


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


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


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


k=\max_{\alpha\in\mathcal{A}}|\alpha|,

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


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


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


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

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


S\vdash^{\ast}u_1Rv_1\vdash^{\ast}u_1z_1v_1,
(8.1)

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


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


R\vdash^{\ast} u_2Qv_2\vdash^{\ast} u_2xQyv_2\vdash^{\ast} u_2xwyv_2,
(8.2)

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


Q\vdash^{\ast} xQy,
(8.3)

Q\vdash^{\ast} w.
(8.4)

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


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


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.
(8.5)

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


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


S\vdash^{\ast} u_1Rv_1\vdash^{\ast} u_1u_2Qv_2v_1\vdash^{\ast} u_1u_2wv_2v_1=uwy
(8.6)

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

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


\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}
(8.7)

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

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


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


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


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


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


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


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


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




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


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


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


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


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


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


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




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


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


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


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

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


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

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




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


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


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




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


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


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




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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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