Языки и трансляции. Мартыненко Б.К. - 22 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

21
Очевидно, что грамматики
G и G
1
имеют один и тот же тип. Действительно,
все правила грамматики
G являются правилами грамматики G
1
. Те же новые
правила, которые имеются в грамматике
G
1
, но отсутствуют в грамматике G,
отличаются от прототипа лишь символом слева, что не может изменить тип
грамматики.
Что и требовалось доказать.
Теорема 2.1. Если L — контекстно-зависимый, контекстно-свободный или
регулярный язык, то языки L ∪ {ε}, L \ {ε} также являются соответственно
контекстно-зависимым, контекстно-свободным или регулярным языками.
Доказательство. Согласно лемме 2.1 существует грамматика G,
порождающая язык
L, начальный нетерминал которой не встречается в правых
частях её правил.
Если язык
L = L(G) не содержит пустого предложения, то мы можем
пополнить грамматику
G ещё одним правилом вида S →ε. Обозначим
пополненную грамматику
G
1
. Правило S →ε может использоваться только как
первое и единственное правило вывода в
G
1
, поскольку начальный нетерминал
S не встречается в правых частях правил. Любой вывод в грамматике G
1
, не
использующий правило
S →ε, есть также вывод в G, так что
L(G
1
)=L(G) ∪ {ε}.
Если же
L = L(G) содержит пустое предложение, то среди правил
грамматики
G имеется правило вида S →ε, с помощью которого только пустое
предложение и выводится. Ни в каком другом выводе это правило не
используется, так что, если его отбросить, то получим грамматику
G
1
, которая
порождает все предложения языка
L, кроме пустого. Следовательно, L(G
1
) =
L(G) \ {ε}.
Согласно лемме 2.1 типы грамматик
G и G
1
одинаковы, поэтому одинаковы
и
типы языков, порождаемых этими грамматиками.
Что и требовалось доказать.
Пример 2.5. Рассмотрим грамматику G из примера 2.2. Перестроим её
согласно лемме 2.1 так, чтобы начальный нетерминал не встречался в правых
частях правил. Обозначим перестроенную грамматику
G
1
.
Очевидно, что
G
1
=(V
N
, V
T
, P
1
, S
1
), где V
N
={S
1
, S, B, C}, V
T
= {a, b, c},
P
1
= { (1) S → aSBC, (2) S → aBC, (3) CB → BC, (4) aB → ab,
(5) bB → bb, (6) bC → bc, (7) cC → cc; (8) S
1
→ aSBC, (9) S
1
→ aBC}.
Построенная грамматика отличается от исходной грамматики
G только
дополнительным нетерминалом
S
1
, используемым в качестве нового
начального символа, и двумя дополнительными правилами (8) и (9), его
определяющими. Согласно лемме 2.1
L(G
1
) = L(G) = {a
n
b
n
с
n
n ≥ 1}.
Можно
добавить пустое предложение к L(G
1
), пополнив грамматику G
1
ещё
одним правилом: S
1
→ε. Обозначим пополненную грамматику G
2
.
Тогда G
2
= (V
N
, V
T
, P
2
, S
1
), где V
N
= {S
1
, S, B, C}, V
T
= {a, b, c},
P
2
= P
1
∪ {S
1
→ ε}.
В силу леммы 2.1 и теоремы 2.1 очевидно, что
L(G
2
) = L(G
1
) ∪ {ε} = {a
n
b
n
с
n
n ≥ 0}.

Страницы