Операции над КС-языками

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

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

Доказательство. Пусть L₁=L(G₁) и L₂=L(G₂) два контекстно - свободных языка, определяемых КС-грамматиками G₁=(V_T1,V_N1,R₁,S₁) и G₂=(V_T2,V_N2,R₂,S₂) соответственно. Проиндексируем нетерминалы грамматики G₁ индексом 1, а нетерминалы G₂ – 2 с тем, чтобы никакие имена различных грамматик не совпадали.

Если объединить нетерминалы, терминалы, правила исходных грамматик и добавить к последнему объединению правило S ® S₁½S₂ , где S - аксиома новой результирующей грамматики, то мы, очевидно, получим КС-грамматику, определяющую объединение языков L₁ и L₂. Действительно, индексирование нетерминалов не изменяет класса исходных грамматик, точно так же как и объединение их правил и добавление контекстно-свободной продукции S ® S₁½S₂.

Последняя продукция и обеспечивает порождение всех цепочек языка L₁ по первой альтернативе правила и всех цепочек языка L₂ по второй его альтернативе.

Таким образом L= L₁ È L₂ = L(G), где

G=( V_T1ÈV_T2,V_N1ÈV_N2,R=R₁ÈR₂È{S®S₁|S₂},S) - КС-грамматика, определяющая объединение языков L₁ и L₂.

Точно также можно показать, что КС-грамматика

G=( V_T1ÈV_T2,V_N1ÈV_N2,R=R₁ÈR₂È{S®S₁S₂},S ) определяет конкатенацию языков L₁ и L₂ (L(G)= L₁ L₂).

Если к правилам P₁ исходной грамматики G₁ добавить правило S ® SS₁½e, считая S начальным символом новой КС-грамматики G, то грамматика G будет определять итерацию языка L₁ - L₁^* . Если же к P₁ добавить правило S ® SS₁½S₁, или правило S ® S₁S½S₁, или правило S ® SS½S₁, то полученная КС-грамматика G будет определять позитивную итерацию L₁⁺.

Если во всех правилах грамматики G₁ вида A ® j ay заменить терминал a на S₂ - аксиому грамматики G₂, то полученная в результате таких преобразований КС-грамматика G будет определять не что иное, как язык L - подстановку языка L₂ в язык L₁ вместо терминала a:

G=<V_T1ÈV_T2\{a},V_N1ÈV_N2,R=R₁ÈR₂È{S®aS₂b}\{S₁®a ab},S>

Для того, чтобы получить грамматику, определяющую обращение L^R для исходного языка L(G) достаточно обратить левые и правые части правил исходной грамматики G, то есть правила a ® b заменить на правила a ^R ® b ^R (в КС-грамматиках правила A ® b заменяются на правила A ® b ^R ). Такие преобразования не изменяют класса КС-грамматик и позволяют порождать все обращенные цепочки. †

Все рассмотренные преобразования КС-грамматик достаточно очевидны. Рассмотрим на примере только формирование грамматики для обращения языка.

Пример 5.2. Пусть задана грамматика с правилами

S ® aS½bB

B ® cB½d

Для простоты здесь взята А-грамматика, но ничто не мешает рассматривать ее как КС-грамматику. Цепочки, порождаемые данной грамматикой состоят из необязательных символов “а” в начале цепочки, символа “b”, затем необязательных символов “c” и символа “d” в конце, т.е. цепочка имеет вид

[aaa...]b[ccc...]d,

где квадратные скобки традиционно обозначают необязательный элемент.

Обратим правила заданной грамматики и в результате получим:

S ® Sa½Bb

B ® Bc½d

Если правила исходной грамматики обеспечивали вывод цепочки слева направо, то полученные правила выводят ее справа налево. Цепочка, порождаемая последней грамматикой имеет вид d[ccc...]b[aaa...]. †

Теорема 5.5. КС-языки не замкнуты относительно операций пересечения, допол нения и разности.

Доказательство. Языки L₁={a ⁿ b ⁿ c ^j½n ³ 1, j ³ 1} и L₂={a ^j b ⁿc ⁿ½n ³ 1, j ³ 1} - КС-языки. Первый из них можно определить правилами

S ® XY

X ® aXb½ab

Y ® cY½c ,

а второй

S ® XY

X ® aX½a

Y ® bYc½bc .

Однако L₁Ç L₂= {aⁿbⁿcⁿ½n ³ 1} - не КС-язык (см. следствие теоремы 5.3). Таким образом, класс КС-языков не замкнут относительно пересечения.

Отсюда можно также заключить, что класс КС-языков не замкнут относительно дополнения. В силу закона де Моргана ( ) любой класс языков, замкнутый относительно объединения и дополнения, должен быть замкнут относительно пересечения. Из теоремы 5.4 известно, что КС-языки замкнуты относительно объединения и предположение об их замкнутости относительно дополнения приводит нас к противоречию с первым доказанным положением данной теоремы.

Для доказательства последнего положения достаточно вспомнить, что дополнение - это, по сути дела, разность множеств. †