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

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

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

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

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


Пересечение контекстно-свободных языков

Пересечение контекстно-свободных языков


Исследуем вопрос о пересечении КС-языков. Введем обозначение: если дан алфавит [math]\{b_1,\ldots,b_k\}[/math], то через [math][b_1^n\ldots,b_k^n][/math] обозначим язык [math]\{b_1^n\ldots,b_k^n\colon n\geqslant0\}[/math].


Теорема 8.10. Класс КС-языков не замкнут относительно пересечения.


Языки [math]a^{\ast}[b^nc^n][/math] и [math][a^nb^n]c^{\ast}[/math], как можно легко доказать, являются КС-языками, но их пересечение есть язык [math][a^nb^nc^n][/math], который — как это было доказано в примере 8.11 — не КС-язык.


Следствие 8.4. Дополнение КС-языка в общем случае не является КС-языком.


Действительно, если бы для любого КС-языка [math]L[/math] его дополнение [math]\overline{L}[/math] было бы КС-языком, то для пересечения любых двух КС-языков [math]L_1[/math] и [math]L_2[/math] мы имели бы: [math]L_1\cap L_2=\overline{\overline{L}_1\cup \overline{L}_2}[/math] — КС-язык, что противоречит теореме 8.10.


Однако оказывается, что класс КС-языков замкнут относительно операции суженного пересечения языков — операции пересечения с регулярными языками.


Теорема 8.11. Если [math]L[/math] — КС-язык, а [math]R[/math] — регулярный язык, то [math]L\cap R[/math] — КС-язык.


Пусть [math]G=(V,N,S,P)[/math] — КС-грамматика, порождающая язык [math]L[/math], а [math]M=(Q,V,q_0,F,\delta)[/math] — конечный автомат, допускающий язык [math]R[/math].


Будем считать, что грамматика [math]G[/math] дана в приведенной форме, причем аксиома не содержится в правых частях правил вывода. Конечный же автомат [math]M[/math] является детерминированным.


В основе конструкции грамматики для пересечения [math]L\cap R[/math] лежит следующая неформальная идея. Мы хотим построить такую КС-грамматику [math]G'[/math], которая порождала бы все цепочки, одновременно порождаемые грамматикой [math]G[/math] и допускаемые конечным автоматом [math]M[/math]. Это значит, что любая цепочка [math]x[/math], порождаемая грамматикой [math]G'[/math], должна удовлетворять двум требованиям: 1) [math]S\vdash_{G}^{\ast}x[/math] и 2) в [math]M[/math] должен найтись единственный путь из начального состояния в одно из заключительных состояний, на котором читается цепочка [math]x[/math]. Если цепочка [math]x[/math] пустая, то она принадлежит пересечению [math]L\cap R[/math] тогда и только тогда, когда в [math]P[/math] есть правило [math]S\to\lambda[/math], а начальное состояние автомата [math]M[/math] является и заключительным. Для непустой цепочки [math]x=x(1)x(2)\ldots x(k)[/math] из пересечения [math]L\cap R[/math] тогда должна существовать единственная последовательность состояний [math]q_0,s_1,\ldots,s_{k-1},q_f~(q_f\in F)[/math] множества [math]Q[/math], в которой


[math]q_0\to_{x(1)}s_1, \quad s_1\to_{x(2)}s_2,\quad \ldots,\quad s_{k-1}\to_{x(k)} q_f.[/math]

Будем тогда в качестве нетерминалов грамматики [math]G'[/math] рассматривать всевозможные упорядоченные тройки вида [math][qXr][/math], где [math]q,\,r[/math] — состояния конечного автомата [math]M[/math], а [math]X[/math] — символ из объединенного алфавита грамматики [math]G[/math] (похожий прием мы применяли, строя КС-грамматику, эквивалентную заданному МП-автомату). Заставим грамматику [math]G'[/math] выводить из аксиомы все непустые цепочки вида


[math]\bigl[q_0x(1)s_1\bigr] \bigl[s_1x(2)s_2\bigr] \ldots \bigl[s_{k-1}x(k)q_f\bigr][/math]

для всех [math]q_f\in F[/math] и всех последовательностей [math]s_1,s_2,\ldots,s_{k-1}[/math] состояний из [math]Q[/math] при условии, что [math]S\vdash_{G}^{\ast}x(1)x(2)\ldots x(k)[/math]. Нетерминал же [math][qar][/math] при [math]a\in V[/math] может быть, по определению, заменен терминалом [math]a[/math] тогда и только тогда, когда в системе команд [math]\delta[/math] конечного автомата [math]M[/math] есть команда [math]qa\to r[/math], т.е. из состояния [math]q[/math] по символу [math]a[/math] можно перейти в состояние [math]r[/math].


При таком определении грамматики [math]G'[/math] она породит непустую терминальную цепочку [math]x[/math] тогда и только тогда, когда [math]x[/math] порождается грамматикой [math]G[/math] и читается на некотором пути из начального состояния в одно из заключительных, — именно тогда (и только тогда) из цепочки [math][q_0x(1)s_1][s_1x(2)s_2]\ldots [s_{k-1}x(k)q_f][/math] может быть выведена сама цепочка [math]x=x(1)x(2)\ldots x(k)[/math]. Образно говоря, грамматика [math]G'[/math] каждый символ непустой цепочки [math]x[/math], порождаемой грамматикой [math]G[/math], помещает между двумя "стражами" — состояниями конечного автомата, и символ может избавиться от этих "стражей" тогда и только тогда, когда в конечном автомате [math]M[/math] есть переход по нему из первого состояния во второе.


Дадим теперь формальное определение грамматики [math]G'\colon[/math]


[math]G'=(V,N',S',P')[/math], где [math]N'=\bigl\{[qXr]\colon q,r\in Q,~ X\in V\cup N\cup \{S'\},~ S'\notin V\cup N\bigr\}[/math]

(аксиома грамматики [math]G'[/math]), а множество правил вывода [math]P'[/math] строится следующим образом:

1) правило вывода [math]S'\to\lambda[/math] принадлежит [math]P'[/math] тогда и только тогда, когда в множестве правил [math]P[/math] грамматики [math]G[/math] есть правило [math]S\to\lambda[/math], а для конечного автомата [math]M[/math] имеет место [math]q_0\in F[/math];


2) для любого правила [math]A\to\gamma[/math] в [math]P~(\gamma\ne\lambda)[/math] в [math]P'[/math] вводится множество всех правил вида


[math][s_1As_{k+1}]\to [s_1\gamma(1)s_2][s_2\gamma(2)s_3] \ldots [s_k\gamma(k)s_{k+1}][/math]

для произвольной последовательности [math]s_1,s_2,\ldots,s_{k+1}[/math] состояний из множества [math]Q[/math] ([math]k\geqslant1[/math] — длина цепочки [math]\gamma[/math]);


3) для любого заключительного состояния [math]q_f\in F[/math] конечного автомата [math]M[/math] в [math]P'[/math] вводится правило вывода [math]S'\to[q_0Sq_f][/math], где [math]S[/math] — аксиома грамматики [math]G[/math];


4) правило вывода [math][qar]\to a[/math] для [math]a\in V[/math] принадлежит [math]P'[/math] тогда и только тогда, когда команда [math]qa\to r[/math] принадлежит системе команд [math]\delta[/math] конечного автомата [math]M[/math];


5) никаких других правил вывода, кроме указанных в пунктах 1-4, множество [math]P'[/math] не содержит.


Непосредственно из построения грамматики [math]G'[/math] видно, что пустая цепочка [math]\lambda[/math] порождается грамматикой [math]G'[/math] тогда и только тогда, когда правило вывода [math]S\to\lambda[/math] содержится в множестве [math]P[/math], то есть [math]\lambda\in L[/math], и конечный автомат [math]M[/math] допускает пустую цепочку, т.е. [math]q_0\in F[/math]. Итак, [math]S'\vdash^{\ast}\lambda[/math] тогда и только тогда, когда [math]\lambda\in L\cap R[/math].


Для непустой цепочки [math]x=x(1)x(2)\ldots x(m)[/math] можно доказать (подробное доказательство мы опускаем*), что [math]S_{G}^{\ast}x[/math], то есть [math]x\in L[/math], тогда и только тогда, когда


[math]S'\vdash [q_0Sq_f]\vdash^{\ast} [q_0x(1)s_1] [q_1x(2)s_2]\ldots [q_{m-1}x(m)s_f][/math] для любых [math]s_1,\ldots,s_{m-1}\in Q[/math].

*Это доказательство без особого труда может быть восстановлено с помощью метода индукции по длине вывода.


Тогда из цепочки [math][q_0x(1)s_1] [q_1x(2)s_2]\ldots [q_{m-1}x(m)s_f][/math] цепочка [math]x=x(1)x(2)\ldots x(m)[/math] может быть выведена в грамматике [math]G'[/math] применением правила, приведенного выше в пункте 4, в том и только в том случае, когда для конечного автомата [math]M[/math] имеет место


[math]q_0\to_{x(1)}s_1\to_{x(2)}s_2\to \ldots\to s_{m-1}\to_{x(m)}q_f[/math]

для некоторых состояний [math]s_1,\ldots,s_{m-1}[/math], то есть [math]x[/math] читается на пути из [math]q_0[/math] в [math]q_f[/math], проходящем через состояния [math]s_1,\ldots,s_{m-1}[/math] и тем самым [math]x\in R[/math], то есть [math]x\in L\cap R[/math].


Итак, окончательно имеем [math]x\in L(G')\leftrightarrow x\in L\cap R[/math].




Пример 8.21. Построим грамматику, порождающую пересечение языка всех палиндромов в алфавите [math]\{a,b\}[/math] с языком [math]a^{\ast}bba^{\ast}[/math].


Грамматику для языка палиндромов задаем в виде


[math]S\to aTa\mid bTb\mid aa\mid bb\mid a\mid b\mid\lambda,\qquad T\to aTa\mid bTb\mid aa\mid bb\mid a\mid b,[/math]

где [math]S[/math] — аксиома. Граф конечного автомата, допускающего язык [math]a^{\ast}bba^{\ast}[/math], приведен на рис. 8.36.


Граф конечного автомата, допускающего язык a*bba*

Согласно правилам построения грамматики [math]G'[/math], изложенным в доказательстве теоремы 8.11, имеем следующую грамматику для пересечения заданных языков:


[math]S'\to [q_0Sq_2],\quad [r_1Sr_4]\to [r_1ar_2] [r_2Tr_3] [r_3ar_4] [r_1br_2] [r_2Tr_3] [r_3br_4][/math]
(8.20)

(для любых последовательностей состояний [math]r_1,r_2,r_3,r_4[/math] конечного автомата);


[math][r_1Sr_3]\to [r_1ar_2][r_1ar_2] [r_1br_2][r_2br_3][/math]

(для любых последовательностей состояний [math]r_1,r_2,r_3[/math] конечного автомата);


[math][r_1Sr_2]\to [r_1ar_2][r_1br_2][/math]

(для любых последовательностей состояний [math]r_1,r_2[/math] конечного автомата);


[math][r_1Sr_4]\to [r_1ar_2] [r_2Tr_3] [r_3ar_4] [r_1br_2] [r_2Tr_3] [r_3br_4][/math]

(для любых последовательностей состояний [math]r_1,r_2,r_3,r_4[/math] конечного автомата);


[math][r_1Tr_3]\to [r_1ar_2][r_1ar_2] [r_1br_2][r_2br_3][/math]
(8.21)

(для любых последовательностей состояний [math]r_1,r_2,r_3[/math] конечного автомата);


[math][r_1Tr_2]\to [r_1ar_2][r_1br_2][/math]

(для любых последовательностей состояний [math]r_1,r_2[/math] конечного автомата);


[math][q_0aq_0]\to a,[/math]
(8.22)

[math][q_0bq_1]\to b,[/math]
(8.23)

[math][q_1bq_2]\to b,[/math]
(8.24)

[math][q_2aq_2]\to a.[/math]
(8.25)

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


[math]S'\vdash [q_0Sq_0]\vdash [q_0aq_0][q_0Tq_2][q_2aq_2]\vdash [q_0aq_0] [q_0bq_1] [q_1bq_2][q_2aq_2].[/math]

На втором шаге написанного выше вывода мы применили первое из правил (8.20) при [math]r_1=r_2=q_0,~ r_3=r_4=q_2[/math], а на третьем шаге — второе правило (8.21) при [math]r_1=q_0,~ r_2=q_1,~ r_3=q_2[/math].


Теперь мы видим, что все "скобки" состояний можно "отряхнуть": последовательно применяя правила (8.22)-(8.25), получаем цепочку [math]abba[/math].


Рассмотрим теперь "неправильную" цепочку [math]aba\notin a^{\ast}bba^{\ast}[/math]. Вывод ее "двойника" может быть таким:


[math]S'\vdash [q_0Sq_2]\vdash [q_0aq_0][q_0Tq_2][q_2aq_2]\vdash [q_0aq_0] [q_0bq_2] [q_2aq_2].[/math]

При выводе мы старались помещать каждый входной символ конечного автомата между такими состояниями, чтобы он входил в метку дуги из первого во второе состояние, но мы видим, что нетерминал [math][q_0bq_2][/math] не может быть заменен ни одним терминалом, и вывод зашел в тупик. Разбор других вариантов вывода "двойника" цепочки [math]aba[/math] мы опускаем. В данном случае оказывается, что любой вывод закончится тупиковой цепочкой.




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


[math]S\to aSa\mid bSb\mid a\mid b\mid\lambda,[/math]

поскольку в этом случае нельзя обойтись без применения правила [math]S\to\lambda[/math] при порождении цепочки четной длины.

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


Следовательно, требование, чтобы грамматика КС-языка [math]L[/math] была задана в приведенной форме и ее единственное разрешенное λ-правило [math]S\to\lambda[/math] применялось только при выводе пустой цепочки, является существенным при построении КС-грамматики для пересечения языка [math]L[/math] с регулярным языком [math]R[/math].


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


Пример 8.22. Докажем, что язык [math]L=\{ww\colon w\in\{a,b\}^{\ast}\}[/math] — так называемый язык двойных слов в алфавите [math]\{a,b\}[/math] — не является контекстно-свободным.


Применить к решению этой задачи сразу лемму о разрастании довольно трудно. Поступим так. Рассмотрим пересечение языка [math]L[/math] с регулярным языком [math]a^{\ast}b^{\ast} a^{\ast}b^{\ast}[/math]. Легко понять, что это пересечение состоит из всех цепочек вида [math]a^mb^na^mb^n[/math] [math](m,n\geqslant0)[/math]. Предполагая, что язык [math]L[/math] контекстно-свободный, получим в силу теоремы 8.11, что контекстно-свободным является и язык [math]\{a^mb^na^mb^n\colon m,n\geqslant0\}[/math]. Однако этот язык не есть КС-язык (см. пример 8.12). Следовательно, не является КС-языком и исходный язык [math]L[/math].


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


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

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