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

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

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

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

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


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

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


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


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


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


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


[math]\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}[/math]

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


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


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


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


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


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


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


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


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


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


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


[math]S\vdash_{G'}^{l-1}\gamma\vdash_{G'}\alpha\,.[/math]

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


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


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


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

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


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

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


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




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


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


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

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


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




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


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

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


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

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


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

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


[math]\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}[/math]
(8.19)

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

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


[math]\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}[/math]

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


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


[math]\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}[/math]

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


[math]S\vdash S_aTS_b\vdash 01TS_b\vdash 01bbS_b\vdash 01bba|[/math]

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


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


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


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


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

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