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

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

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

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


Основное свойство суперпозиции КС-языков

Основное свойство суперпозиции КС-языков


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


Теорема 8.9. Если языки L_{a_i},~i=\overline{1,n}, контекстно-свободные, язык L также контекстно-свободный, то суперпозиция \mathcal{S}(L, L_{a_1}, \ldots,L_{a_n}) есть КС-язык.


Пусть V=\{a_1,\ldots,a_n\} и каждый язык L_{a_i},~i=\overline{1,n}, задается КС-грамматикой G_{a_i}=(V_{a_i},N_{a_i},S_{a_i},P_{a_i}), а язык L задается КС-грамматикой G=(V,N,S,P). Без ограничения общности можно предполагать, что нетерминальные алфавиты всех указанных грамматик попарно не пересекаются (так как всегда можно провести процедуру переименования нетерминалов любой грамматики).


Построим следующую грамматику: G'=(V',N',S,P'), где


\begin{gathered}V'=V_{a_1}\cup\ldots\cup V_{a_n},\qquad N'=N\cup N_{a_1}\cup \ldots\cup N_{a_n},\\ P'=P_{a_1}\cup\ldots\cup P_{a_n}\cup \{A\to\alpha'\colon\, \forall A\to\alpha\in P\}.\end{gathered}

Здесь цепочка \alpha' получается из цепочки \alpha следующим образом: все нетерминалы в \alpha остаются без изменений, а каждое вхождение каждого терминала b\in V, то есть b=a_i для некоторого i= \overline{1,n}, заменяется аксиомой S_b грамматики G_b (заметим, что, согласно этим правилам замены, для любых цепочек \alpha,\beta в объединенном алфавите грамматики G имеем (\alpha\beta)'=\alpha'\beta' и \lambda'=\lambda).


Неформально система правил P' получается объединением всех множеств правил грамматик G_{a_i} и добавлением "перекрашенных" правил грамматики G. "Перекрашивание" выражается в том, что каждый терминал a_i грамматики G заменяется аксиомой S_{a_i} грамматики G_{a_i}, а, нетерминалы остаются в неприкосновенности. В частности, для любой цепочки \beta\in N^{\ast} имеет место \beta'=\beta.


Докажем теперь, что грамматика G', контекстно-свободная по построению, является искомой, т.е. она порождает суперпозицию \mathcal{S}(L,L_{a_1},\ldots,L_{a_n}).


Прежде всего докажем, что для произвольных нетерминала A\in N и цепочки \gamma\in(V\cup N)^{\ast} из A\vdash_{G}^{\ast}\gamma следует A\vdash_{G'}^{\ast}\gamma', т.е. если в грамматике G из нетерминала A выводится цепочка \gamma в объединенном алфавите, то в грамматике G' из того же нетерминала A выводится "двойник" цепочки \gamma получаемый из последней заменой каждого ее терминального символа b аксиомой соответствующей грамматики G_b=G_{a_i} для некоторого i=\overline{1,n}.


Доказательство проведем индукцией по длине l вывода цепочки \gamma из нетерминала A. Для вывода нулевой длины утверждение тривиально, так как A\vdash^{0}A=A'. Пусть утверждение доказано при всех l\leqslant m-1, и пусть A\vdash_G^m\gamma. Тогда существует цепочка \xi, такая, что A\vdash_{G}^{m-1}\xi\vdash_{G}\gamma. Согласно предположению индукции, отсюда следует, что A\vdash_{G'}^{\ast}\xi', а так как \xi\vdash_{G}\gamma, то существует такое правило вывода B\to\beta в множестве P, что \xi=\xi_1B\xi_2 (для некоторых \xi_1,\xi_2\in(V\cup N)^{\ast}) и \gamma=\xi_1\beta\xi_2. Следовательно, \xi'=\xi'_1B\xi'_2, а так как в множестве правил вывода P' есть правило B\to\beta', то \xi'\vdash_{G'}\xi'_1\beta'\xi'_2=\gamma'. Итак, окончательно получаем A\vdash_{G'}^{\ast}\xi'\vdash_{G'}\gamma'.


Из доказанного следует, что для любой цепочки x\in L=L(G), т.е. такой цепочки x, что S\vdash_{G}^{\ast}x, выполняется S\vdash_{G'}^{\ast}x'. Если x=\lambda, то тогда из \lambda\in L следует, что \lambda\in L(G'). Если x\ne\lambda, тогда для некоторого k>0 имеем x=x(1)\ldots x(k) и x'=S_{x(1)}\ldots S_{x(k)}, а так как для каждого j=\overline{1,k} выполняется S_{x(j)}\vdash_{G'}^{\ast}y_j, какова бы ни была цепочка y_j\in L_{x(j)}, то x'\vdash_{G'}^{\ast}y_1\ldots y_k. Но последняя цепочка есть произвольная цепочка суперпозиции \mathcal{S}(L,L_{a_1},\ldots,L_{a_n}) (не считая пустой цепочки, непосредственно выводимой из аксиомы S), так как она получена из произвольной непустой цепочки x языка L путем замены в ней каждого символа x(j) произвольной цепочкой языка L_{x(j)}. Поскольку из S\vdash_{G}\lambda следует S\vdash_{G'}\lambda любая цепочка суперпозиции \mathcal{S}(L,L_{a_1},\ldots,L_{a_n}) порождается грамматикой G'.


Докажем теперь, что если цепочка w в алфавите V' (терминальном алфавите грамматики G') выводится из аксиомы S в грамматике G', то она принадлежит суперпозиции \mathcal{S}(L,L_{a_1}, \ldots, L_{a_n}). Для этого сначала докажем, что для любых нетерминала A\in N и цепочки \gamma\in(V\cup N)^{\ast} из A\vdash_{G'}^{\ast}\gamma' следует A\vdash_{G}^{\ast}\gamma.


Опять воспользуемся индукцией по длине вывода, но на этот раз вывода цепочки \gamma' из нетерминала A в грамматике G'. Случай вывода нулевой длины, как и выше, тривиален. Пусть для некоторого m>0 выполняется A\vdash_{G'}^{m}\gamma'. Тогда существует такая цепочка \mu, что A\vdash_{G'}^{m-1}\mu\vdash_{G'}\gamma'. Каждый символ цепочки \gamma' есть либо одна из аксиом S_{a_i},~i=\overline{1,n}, либо нетерминал из N. Так как КС-грамматики G и G_{a_i},~ i=\overline{1,n}, в силу результатов, полученных в 8.2, можно считать заданными в приведенной форме, то правые части правил вывода каждой из рассматриваемых грамматик не содержат аксиомы. Кроме того, нетерминальные алфавиты N и N_{a_i} всех этих грамматик попарно не пересекаются.


Отсюда следует, что цепочка \gamma' не может быть непосредственно выведена из цепочки \mu применением какого-либо правила из множества P_{a_i}, т.е. какого-либо правила вывода грамматики G_{a_i}, а выводится из \mu применением некоторого правила вида B\to\beta', построенного, как указано в определении грамматики G', по правилу B\to\beta системы правил грамматики G. Тогда мы можем написать: \gamma'=\gamma'_1 \beta' \gamma'_2 (для некоторых цепочек \gamma_1 и \gamma_2 в алфавите V\cup N), \mu=\gamma'_1B \gamma'_2= (\gamma_1B \gamma_2)'. Это значит, что \mu=\xi' при \xi=\gamma_1B \gamma_2, то есть A\vdash_{G'}^{m-1}\xi'. Согласно предположению индукции, отсюда следует, что A\vdash_{G}^{\ast}\xi, а так как \xi=\gamma_1B \gamma_2 и в множестве правил вывода грамматики G содержится правило B\to\beta, то \xi\vdash_{G}\gamma_1\beta\gamma_2=\gamma и окончательно A\vdash_{G}^{\ast}\gamma. В частности, отсюда следует, что для произвольной цепочки x\in V^{\ast}, такой, что S\vdash_{G'}^{\ast}\xi', имеет место S\vdash_{G}^{\ast}\xi, то есть x\in L.


Теперь докажем, что произвольная цепочка \alpha, выводимая в грамматике G' из аксиомы S, имеет вид \alpha_1\alpha_2\ldots\alpha_m~ (m\geqslant1), где для каждого j=\overline{1,m} цепочка \alpha_j либо пуста, либо для некоторого символа b_j\in V выводится из аксиомы S_{b_j}. грамматики G_{b_j}, то есть S_{b_j}\vdash_{G_{b_j}}^{\ast}\alpha_j, либо является некоторой цепочкой нетерминалов из N. Действительно, сама аксиома S удовлетворяет этому требованию. Далее, пусть доказываемое справедливо для любой цепочки, выводимой в G' за любое число шагов, не превышающее l-1 для некоторого l>1.


Предположим, что S\vdash_{G'}^{l}\alpha. Тогда, как это мы уже делали в аналогичных ситуациях, рассмотрим последний шаг этого вывода, т.е. для некоторой цепочки \gamma будем иметь


S\vdash_{G'}^{l-1}\gamma\vdash_{G'}\alpha\,.

Согласно предположению индукции, цепочка j представима в виде \gamma=\gamma_1 \gamma_2\ldots\gamma_m, где \gamma_j=\lambda,~ j=\overline{1,m}, или S_{b_j}\vdash_{G_{b_j}}^{\ast}\gamma_j для некоторого b_j\in V, или \gamma\in N^{\ast}. Так как к цепочке \gamma применяется некоторое правило грамматики G' (на последнем шаге вывода цепочки \alpha из аксиомы S), то в \gamma входит по крайней мере один нетерминал грамматики G'. Если это есть некоторый символ A\in N, то он может входить только в одну из таких подцепочек \gamma_j, которая состоит из нетерминалов алфавита N. После замены A посредством некоторого правила вида A\to\beta', соответствующего правилу A\to\beta грамматики G, получится цепочка, в которую могут входить только нетерминалы множества N и аксиомы S_b грамматик G_b для каких-либо b\in N.


Следовательно, если цепочка \alpha на последнем шаге ее вывода из аксиомы получена применением некоторого правила A\to\beta', то она также может быть представлена соединением цепочек такого же вида, что и цепочки \gamma_j.


Если же S_{b_j}\vdash_{G_{b_j}}^{\ast}\gamma_j для некоторого b_j\in V и на указанном шаге применяется правило из множества P_{b_j}, то оно, ввиду того что все множества N и N_b (для различных b\in N) попарно не пересекаются, может быть применено только к такой подцепочке \gamma_j, которая выводится из аксиомы S_{b_j}, и тогда в цепочке а получим подцепочку, опять-таки выводимую из S_{b_j}, т.е. и в этом случае* цепочка \alpha образуется соединением подцепочек того же вида, что и цепочки \gamma_j.


*Заметим, что в приведенном выше доказательстве существенно используется тот факт, что нетерминальные алфавиты N,N_{a_1},\ldots,N_{a_n} попарно не пересекаются. Бели бы это было не так, то в некоторой подцепочке \gamma_j, выводимой из аксиомы S_{b_j} для некоторого b_j\in V, мы могли бы заменить вхождение нетерминала из N_{b_j} применив правило вывода "чужой" грамматики G_{a_k},~a_k\ne b_j и получить в составе цепочки а подцепочку, не выводимую ни из одной "дочерней" аксиомы S_b,~b\in V.

Пусть теперь цепочка w\in V^{\prime\ast} такова, что S\vdash_{G'}^{\ast}w. Если w=\lambda и S\vdash_{G'}\lambda, то это означает наличие правила вывода S\to\lambda в множестве P' и, следовательно, в множестве P, то есть \lambda\in L и \mathcal{S}(L,L_{a_1}, \ldots, L_{a_n}). Таким образом в этом случае пустая цепочка, порождаемая грамматикой G', действительно принадлежит указанной суперпозиции. Иначе в силу доказанного выше свойства любой цепочки, выводимой в грамматике G' из аксиомы, цепочка w, не содержащая по условию вхождений нетерминалов из N, допускает представление в виде w_1w_2\ldots w_k, где для каждого j=\overline{1,k} имеет место выводимость S_{b_j}\vdash_{G_{b_j}}^{\ast} w_j (возможно для некоторых j, что w_j=\lambda; в частности, может оказаться, что и w=\lambda). Таким образом,


S\vdash_{G'}^{\ast}S_{b_1}S_{b_2}\ldots S_{b_k}\vdash_{G'}^{\ast} w_1w_2\ldots w_k,

где для каждого j=\overline{1,k} цепочка w_j принадлежит языку L_{b_j}. Так как при этом S\vdash_{G}^{\ast}b_1b_2\ldots b_k, то есть b_1b_2\ldots b_k\in L, то w\in\mathcal{S}(L,L_{a_1},\ldots, L_{a_n}).


Итак, доказав, что любая цепочка w в терминальном алфавите V' грамматики G', выводимая из аксиомы, есть элемент суперпозиции \mathcal{S}(L,L_{a_1},\ldots,L_{a_n}), мы тем самым завершили доказательство теоремы.




Следствие 8.3. Семейство КС-языков замкнуто относительно операций объединения, соединения, итерации и позитивной итерации.


Доказательство получается немедленно из приведенных выше определений операций объединения, соединения, итерации и позитивной итерации как частных случаев суперпозиции.


Вывод цепочки из суперпозиции

Заметим, что объединение бесконечного семейства КС-языков не является, вообще говоря, КС-языком. Так, язык \{a^nb^nc^n\colon n\geqslant0\}, не являющийся КС-языком, может быть представлен в виде объединения счетного семейства, каждый элемент которого есть язык \{a^nb^nc^n\} для фиксированного натурального n, т.е. язык, состоящий из одной цепочки, а следовательно, регулярный и контекстно-свободный.


Замечание 8.12. Вывод цепочки w из суперпозиции \mathcal{S}(L,L_{a_1},\ldots, L_{a_n}) (если она не является пустой цепочкой, непосредственно выводимой из аксиомы S) в грамматике G', построенной в доказательстве теоремы 8.9, можно провести по "двухуровневой" схеме, приведенной на рис. 8.34. Сначала порождаем, используя "перекрашенные" правила грамматики G, т.е. правила вида A\to j' для A\in N и \gamma\in(V\cup N)^{\ast}, "двойника" произвольной цепочки x\in L, т.е. цепочку S_{x(1)}\ldots S_{x(k)}. Из нее затем, используя правила "дочерних" грамматик, порождаем саму цепочку w, из каждой аксиомы S_{x(j)} выводя некоторую цепочку y_j так, что w=y_1\ldots y_k.




Пример 8.20. Рассмотрим конструкцию из доказательства теоремы 8.9 на конкретном примере. Язык L определим как язык, порождаемый грамматикой G со следующим множеством правил вывода: S\to ab\mid aSb\mid SS. Языки L_a и L_b определим так:


L_a=\{0^n1^n\colon n\geqslant0\},\qquad L_b=\{x\colon x\in\{a,b\},~ x=x^R\}

(т.е. L_b есть язык палиндромов в алфавите \{a,b\}). Запишем множества правил вывода грамматик G_a и G_b, порождающих языки L_a и L_b соответственно:


S\to 0S1\mid 01\mid\lambda (грамматика G_a) и S\to aSa\mid bSb\mid aa\mid bb\mid a\mid b\mid\lambda (грамматика G_b).

Преобразуя грамматики G,\,G_a и G_b к приведенной форме (убирая аксиому из правых частей правил вывода) и переименовывая нетерминалы так, чтобы множества N,\,N_a и N_b попарно не пересекались, построим, как описано в доказательстве теоремы 8.9, множество P' правил вывода грамматики


G'=\bigl(\{0,1,a,b\}, \{S,T,S_a,T_a,S_b,T_b\}, S,P'\bigr),

порождающей суперпозицию \mathcal{S}(L,L_a,L_b)\colon


\begin{cases}S\to S_aS_b\mid S_aTS_b\mid TT,\\ T\to S_aS_b\mid S_aTS_b\mid TT,\\ S_a\to 0T_a1\mid 01\mid\lambda,\\ T_a\to 0T_a1\mid 01,\\ S_b\to aT_ba\mid bT_bb\mid aa\mid bb\mid a\mid b\mid 0\mid\lambda,\\ T_b\to aT_ba\mid bT_bb\mid aa\mid bb\mid a\mid b\mid 0.\end{cases}
(8.19)

Дерево вывода цепочки 010011abab

Рассмотрим дерево вывода цепочки 010011abab, изображенное на рис. 8.35. Если при порождении этой цепочки использовать "двухуровневую" схему, описанную в замечании 8.12, то получим такой вывод:


\begin{aligned}S&\vdash S_aTS_b\vdash S_aS_aS_bS_b\vdash 01S_aS_bS_b\vdash 010T_a1S_bS_b\vdash 010011S_bS_b\vdash\\ &\vdash 010011aT_baS_b\vdash 010011abaS_b\vdash 010011abab.\end{aligned}

Сначала порождается "двойник" цепочки abab\in L, а затем на место первого символа (замененного аксиомой S_a "дочерней" грамматики G_a) подставляется цепочка 01, на место второго символа — цепочка 0011, на место третьего — aba, на место четвертого — цепочка b.


Заметим, что в общем случае построения вывода в грамматике G' (если не обязательно придерживаться "двухуровневой" стратегии) "дочерняя" грамматика может начать "работать", как только в выводе появляется ее аксиома. Так, по изображенному на рис. 8.35 дереву вывода может быть построен следующий левый вывод:


\begin{aligned}S&\vdash S_aTS_b\vdash 01S_aS_bS_b\vdash 010T_a1S_bS_b\vdash 010011S_bS_b\vdash\\ &\vdash 010011aT_baS_b\vdash 010011abaS_b\vdash 010011abab.\end{aligned}

Но если мы пренебрежем требованием, чтобы нетерминальные алфавиты грамматик G,\,G_a и G_b попарно не пересекались, и отождествим, скажем, нетерминалы T_a,\,T_b и T, положив T_a=T_b=T, то сможем вывести цепочку, не принадлежащую суперпозиции \mathcal{S}(L,L_a,L_b). Например,


S\vdash S_aTS_b\vdash 01TS_b\vdash 01bbS_b\vdash 01bba|

В самом деле, цепочка 01 может быть получена применением либо правила S_a\to01, либо правила T_a\to01; цепочка bb — применением правила T_b\to bb или S_b\to bb, цепочка a — применением правила S_b\to a или T_b\to a. Можно легко убедиться в том, что в этом случае единственная цепочка, состоящая из аксиом "дочерних" грамматик, т.е. символов S_a,\,S_b, из которой может быть выведена цепочка 01bba, равна S_aS_bS_b. Но эта цепочка не выводима из аксиомы S. Если же мы, анализируя цепочку 01bba, стали бы рассматривать в качестве правой части правила вывода не цепочку bb, а цепочку b, то получили бы подцепочку ba, не являющуюся правой частью ни одного правила вывода, и тогда имели бы S_aS_bba — цепочку, не выводимую из аксиомы S.


Мы вывели "плохую" цепочку здесь потому, что "перепутав" нетерминалы грамматик, позволили "вклиниться" "дочерней" грамматике G_b в работу грамматики "верхнего уровня". Аналогично можно построить пример, когда разные "дочерние" грамматики "мешают" друг другу.


Итак, требование, согласно которому нетерминальные алфавиты грамматик G и всех G_{a_i} попарно не пересекаются, является существенным.

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

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


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

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