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

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

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

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


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

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


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


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


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


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


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


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


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


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


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


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


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.

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


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

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


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


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


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

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


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


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


[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}]

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


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


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


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


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


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


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] для любых s_1,\ldots,s_{m-1}\in Q.

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


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


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

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


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




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


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


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,

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


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

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


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]
(8.20)

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


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

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


[r_1Sr_2]\to [r_1ar_2][r_1br_2]

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


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

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


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

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


[r_1Tr_2]\to [r_1ar_2][r_1br_2]

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


[q_0aq_0]\to a,
(8.22)

[q_0bq_1]\to b,
(8.23)

[q_1bq_2]\to b,
(8.24)

[q_2aq_2]\to a.
(8.25)

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


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].

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


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


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


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].

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




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


S\to aSa\mid bSb\mid a\mid b\mid\lambda,

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


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


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


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


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


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

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

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


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

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