Пересечение контекстно-свободных языков
Исследуем вопрос о пересечении КС-языков. Введем обозначение: если дан алфавит , то через обозначим язык .
Теорема 8.10. Класс КС-языков не замкнут относительно пересечения.
Языки и , как можно легко доказать, являются КС-языками, но их пересечение есть язык , который — как это было доказано в примере 8.11 — не КС-язык.
Следствие 8.4. Дополнение КС-языка в общем случае не является КС-языком.
Действительно, если бы для любого КС-языка его дополнение было бы КС-языком, то для пересечения любых двух КС-языков и мы имели бы: — КС-язык, что противоречит теореме 8.10.
Однако оказывается, что класс КС-языков замкнут относительно операции суженного пересечения языков — операции пересечения с регулярными языками.
Теорема 8.11. Если — КС-язык, а — регулярный язык, то — КС-язык.
Пусть — КС-грамматика, порождающая язык , а — конечный автомат, допускающий язык .
Будем считать, что грамматика дана в приведенной форме, причем аксиома не содержится в правых частях правил вывода. Конечный же автомат является детерминированным.
В основе конструкции грамматики для пересечения лежит следующая неформальная идея. Мы хотим построить такую КС-грамматику , которая порождала бы все цепочки, одновременно порождаемые грамматикой и допускаемые конечным автоматом . Это значит, что любая цепочка , порождаемая грамматикой , должна удовлетворять двум требованиям: 1) и 2) в должен найтись единственный путь из начального состояния в одно из заключительных состояний, на котором читается цепочка . Если цепочка пустая, то она принадлежит пересечению тогда и только тогда, когда в есть правило , а начальное состояние автомата является и заключительным. Для непустой цепочки из пересечения тогда должна существовать единственная последовательность состояний множества , в которой
Будем тогда в качестве нетерминалов грамматики рассматривать всевозможные упорядоченные тройки вида , где — состояния конечного автомата , а — символ из объединенного алфавита грамматики (похожий прием мы применяли, строя КС-грамматику, эквивалентную заданному МП-автомату). Заставим грамматику выводить из аксиомы все непустые цепочки вида
для всех и всех последовательностей состояний из при условии, что . Нетерминал же при может быть, по определению, заменен терминалом тогда и только тогда, когда в системе команд конечного автомата есть команда , т.е. из состояния по символу можно перейти в состояние .
При таком определении грамматики она породит непустую терминальную цепочку тогда и только тогда, когда порождается грамматикой и читается на некотором пути из начального состояния в одно из заключительных, — именно тогда (и только тогда) из цепочки может быть выведена сама цепочка . Образно говоря, грамматика каждый символ непустой цепочки , порождаемой грамматикой , помещает между двумя "стражами" — состояниями конечного автомата, и символ может избавиться от этих "стражей" тогда и только тогда, когда в конечном автомате есть переход по нему из первого состояния во второе.
Дадим теперь формальное определение грамматики
, где
(аксиома грамматики ), а множество правил вывода строится следующим образом:
1) правило вывода принадлежит тогда и только тогда, когда в множестве правил грамматики есть правило , а для конечного автомата имеет место ;
2) для любого правила в в вводится множество всех правил вида
для произвольной последовательности состояний из множества ( — длина цепочки );
3) для любого заключительного состояния конечного автомата в вводится правило вывода , где — аксиома грамматики ;
4) правило вывода для принадлежит тогда и только тогда, когда команда принадлежит системе команд конечного автомата ;
5) никаких других правил вывода, кроме указанных в пунктах 1-4, множество не содержит.
Непосредственно из построения грамматики видно, что пустая цепочка порождается грамматикой тогда и только тогда, когда правило вывода содержится в множестве , то есть , и конечный автомат допускает пустую цепочку, т.е. . Итак, тогда и только тогда, когда .
Для непустой цепочки можно доказать (подробное доказательство мы опускаем*), что , то есть , тогда и только тогда, когда
для любых .
*Это доказательство без особого труда может быть восстановлено с помощью метода индукции по длине вывода.
Тогда из цепочки цепочка может быть выведена в грамматике применением правила, приведенного выше в пункте 4, в том и только в том случае, когда для конечного автомата имеет место
для некоторых состояний , то есть читается на пути из в , проходящем через состояния и тем самым , то есть .
Итак, окончательно имеем .
Пример 8.21. Построим грамматику, порождающую пересечение языка всех палиндромов в алфавите с языком .
Грамматику для языка палиндромов задаем в виде
где — аксиома. Граф конечного автомата, допускающего язык , приведен на рис. 8.36.
Согласно правилам построения грамматики , изложенным в доказательстве теоремы 8.11, имеем следующую грамматику для пересечения заданных языков:
(8.20)
(для любых последовательностей состояний конечного автомата);
(для любых последовательностей состояний конечного автомата);
(для любых последовательностей состояний конечного автомата);
(для любых последовательностей состояний конечного автомата);
(8.21)
(для любых последовательностей состояний конечного автомата);
(для любых последовательностей состояний конечного автомата);
Рассмотрим пример порождения какой-нибудь цепочки из определенного выше пересечения двух языков. Возьмем цепочку . Выведем сначала "двойника" этой цепочки, в котором каждый символ "окружен" состояниями конечного автомата. В процессе вывода мы стараемся "положить" нашу цепочку на некоторый путь из начальной вершины автомата в заключительную:
На втором шаге написанного выше вывода мы применили первое из правил (8.20) при , а на третьем шаге — второе правило (8.21) при .
Теперь мы видим, что все "скобки" состояний можно "отряхнуть": последовательно применяя правила (8.22)-(8.25), получаем цепочку .
Рассмотрим теперь "неправильную" цепочку . Вывод ее "двойника" может быть таким:
При выводе мы старались помещать каждый входной символ конечного автомата между такими состояниями, чтобы он входил в метку дуги из первого во второе состояние, но мы видим, что нетерминал не может быть заменен ни одним терминалом, и вывод зашел в тупик. Разбор других вариантов вывода "двойника" цепочки мы опускаем. В данном случае оказывается, что любой вывод закончится тупиковой цепочкой.
Заметим, что в рассмотренном примере конструкцию теоремы нельзя применять к грамматике языка палиндромов, если она задана в виде
поскольку в этом случае нельзя обойтись без применения правила при порождении цепочки четной длины.
Так как при построении грамматики правила с пустой правой частью (из множества правил грамматики ) никак не преобразуются, грамматика в таком случае не породит "двойника" ни одной цепочки четной длины языка палиндромов.
Следовательно, требование, чтобы грамматика КС-языка была задана в приведенной форме и ее единственное разрешенное λ-правило применялось только при выводе пустой цепочки, является существенным при построении КС-грамматики для пересечения языка с регулярным языком .
Доказанное утверждение о "контекстной свободности" пересечения КС-языка с любым регулярным языком в совокупности с леммой о разрастании для КС-языков полезно при доказательстве утверждений о том, что какой-либо язык не является контекстно-свободным.
Пример 8.22. Докажем, что язык — так называемый язык двойных слов в алфавите — не является контекстно-свободным.
Применить к решению этой задачи сразу лемму о разрастании довольно трудно. Поступим так. Рассмотрим пересечение языка с регулярным языком . Легко понять, что это пересечение состоит из всех цепочек вида . Предполагая, что язык контекстно-свободный, получим в силу теоремы 8.11, что контекстно-свободным является и язык . Однако этот язык не есть КС-язык (см. пример 8.12). Следовательно, не является КС-языком и исходный язык .
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|