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

UptoLike

ВУЗ: 

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

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

Рубрика: 

20
§ 2.4. Пустое предложение
Легко заметить по тому, как определены грамматики, что пустое предложе-
ние (
ε) не находится ни в контекстно-свободном, ни в контекстно-зависимом
языках, ни в регулярном множестве. Мы расширим данные ранее определения
этих классов грамматик, допустив порождение пустого предложения посред-
ством правила вида
S →ε, где S — начальный символ, при условии, что S не
появляется в правой части никакого правила. В этом случае ясно, что правило
S →ε может использоваться только на первом шаге вывода и только на нём.
Имеет место следующая лемма.
Лемма 2.1. Если G=(V
N
, V
T
, P, S) есть контекстно-зависимая, контек-
стно-свободная или регулярная грамматика, то существует другая
грамматика G
1
такого же типа, которая порождает тот же самый язык и в
которой ни одно правило не содержит начальный символ в своей правой
части.
Доказательство. Пусть
S
1
— символ, не принадлежащий ни алфавиту
нетерминалов, ни алфавиту терминалов грамматики
G.
Положим
G
1
=(V
N
∪ { S
1
},V
T
, P
1
, S
1
). Множество правил P
1
состоит из всех
правил
P и правил вида S
1
→α при условии, что S → α ∈ P. Поскольку символ
S
1
∉V (V = V
N
∪ V
T
), то он не появляется в правой части никакого правила из
множества
P
1
.
Докажем, что
L(G)=L(G
1
).
I. Покажем сначала, что
L(G) ⊆ L(G
1
).
Пусть
x ∈ L(G), т.е. S
x. Пусть первое используемое правило есть S →α∈P.
Тогда S
α
x. По построению P
1
правило S
1
→α∈P
1
, так что S
1
α.
Поскольку любое правило грамматики G является также правилом грам-
матики
G
1
, то α
x.
Таким образом, имеем
S
1
x, т.е. x∈ L(G
1
), и тем самым доказано, что
L(G) ⊆ L(G
1
).
II. Покажем теперь, что
L(G
1
)
⊆
L(G).
Пусть
x ∈ L(G
1
), т. е. S
1
x. Пусть первое используемое правило есть S
1
→ α.
Но такое правило существует во множестве
P
1
только потому, что в правилах P
имеется правило
S →α. Следовательно, S
α.
С другой стороны,
α
x и α не содержит символа S
1
. Поскольку ни одно
правило из множества
P
1
не содержит справа символа S
1
, то ни одна сентен-
циальная форма этого вывода также не содержит символа
S
1
. Значит, в этом
выводе используются только такие правила, которые имеются во множестве P.
Поэтому
α
x. С учётом того, что S
α, получаем вывод S
α
x. Это и
означает, что
L(G
1
)
⊆
L(G).
Из утверждений I и II следует, что
L(G) = L(G
1
).
*
G
⇒
*
G
⇒
G
⇒
1
G
⇒
1
*
G
⇒
1
*
G
⇒
G
⇒
*
G
⇒
1
*
G
⇒
1
*
G
⇒
G
⇒
G
⇒
*
G
⇒

Страницы