Теорема 7.1. Семейство КС–языков замкнуто относительно операций объедине-
ния, произведения, итерации и усеченной итерации.
Доказательство. Язык является контекстно–свободным, если существует КС–
грамматика, порождающая его. Пусть L
1
и L
2
— КС–языки, тогда существуют КС–
грамматики
G
1
= (V
T 1
, V
N1
, P
1
, S
1
) и G
2
= (V
T 2
, V
N2
, P
2
, S
2
) ,
порождающие соответственно L
1
и L
2
. Всегда можно считать, что множества нетер-
минальных символов этих КС–грамматик не пересекаются и V
N1
∩V
N2
= ∅. Рассмот-
рим КС–грамматику
G = (V
T 1
∪ V
T 2
, V
N1
∪ V
N2
∪ {S|S ̸∈ V
T
∪ V
N
}, P, S),
где S — новый нетерминал, а P — множество правил, полученное объединением
правил исходных грамматик и двух новых правил S → S
1
|S
2
, т.е.
P = P
1
∪ P
2
∪ {S → S
1
, S → S
2
}.
Любой вывод в G имеет вид S ⇒ S
1
∗
⇒ x или S ⇒ S
2
⇒
∗
y, причем S
1
∗
⇒ x — это
всегда вывод в G
1
, а S
2
∗
⇒ y — это всегда вывод в G
2
, т.к. множества нетерминальных
символов V
N1
и V
N2
не пересекаются. Тогда L(G) = L(G
1
) ∪ L(G
2
).
Аналогично можно показать, что язык L
1
L
2
порождается грамматикой G, мно-
жество правил которой содержит кроме P
1
и P
2
правило S → S
1
S
2
.
Можно также показать язык L
+
1
порождается грамматикой, множество правил
которой, кроме правил P
1
, содержит два дополнительных правила S → SS
1
|S
1
, а
язык L
∗
1
— грамматикой с дополнительными правилами S → SS
1
|ε .
Операции произведения, усеченной итерации, итерации и объединения позволяют
легко строить КС–грамматики сложных языков через грамматики простых языков.
Например, пусть требуется построить КС–грамматику, порождающую идентифика-
торы языка Паскаль.
Идентификатор — это последовательность цифр и букв, начинающаяся с бук-
вы, следовательно, идентификатор можно определить как произведение понятия
<буква> и понятия <знаки>. Знаки — это произвольная последовательность букв и
цифр, в том числе и пустая, следовательно <знаки> — итерация элемента <знак>,
в качестве которого могут выступать буквы и цифры. Тогда получим грамматику
G : < идентификатор >→< буква >< знаки >
< знаки >→< знак >< знаки > |ε
< знак >→< буква > | < цифра >
< буква >→ A|B|...|Z
< цифра >→ 0|1|...|9
Рассмотрим операции дополнения и пересечения, выполняемые над КС–языками.
Чтобы доказать незамкнутость семейства КС–языков относительно этих операций,
сформулируем пока без доказательства следующую теорему (доказательство рас-
смотрим далее в параграфе 7.6).
Теорема 7.2. Язык a
n
b
n
c
n
, n > 0 в алфавите {a,b,c} не является контекстно–
свободным.
Теорема 7.3. Семейство КС–языков не замкнуто относительно операции пере-
сечения.
Доказательство. Для доказательства достаточно привести хотя бы один пример
таких КС–языков L
1
и L
2
, пересечение которых не является КС–языком. Рассмотрим
192