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

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

Теорема 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 a b }, 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 известно, что КС-языки замкнуты относительно объединения и предположение об их замкнутости относительно дополнения приводит нас к противоречию с первым доказанным положением данной теоремы.

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