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

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

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

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

Если объединить нетерминалы, терминалы, правила исходных грамматик и добавить к последнему объединению правило

S ® S₁ ½ S₂,

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

S ® S₁ ½ S₂.

Последняя продукция и обеспечивает порождение всех цепочек языка L₁ по первой альтернативе правила и всех цепочек языка L₂ по второй его альтернативе. Таким образом L= L₁ È L₂ = L(G), где

G=(N₁ÈN₂,S₁ÈS₂,P₁È P₂ È {S ® S₁½S₂},S) -

КС-грамматика, определяющая объединение языков L₁ и L₂.

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

G=(N₁ÈN₂,S₁ÈS₂,P₁È P₂ È {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.

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

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

Дата добавления: 2015-06-27