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

UptoLike

ВУЗ: 

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

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

Рубрика: 

64
Понятия, касающиеся деревьев вывода для КС-грамматик, непосред-
ственно переносятся на эти расширенные грамматики. Просто разрешается
использовать обозначение ε в качестве метки узла. Ясно, что такой узел должен
быть листом.
Теорема 4.11. Если L — язык, порождаемый грамматикой G =(V
N
, V
T
, P, S),
и каждое правило в P имеет вид A →α, где A — нетерминал, а α∈V
*
(α = ε
допустимо), то L может быть порожден грамматикой, в которой каждое
правило имеет вид A →α, где A — нетерминал, а α∈V
+
, либо S →ε и, кроме
того, начальный нетерминал грамматики S не появляется в правой части
никакого правила.
Доказательство. При помощи тривиального расширения леммы 2.1 мы
можем предположить, что S не появляется справа ни в одном правиле в P. Для
любого нетерминала A∈V
N
мы можем решить, существует ли вывод A
ε,
поскольку если такой вывод существует, то существует и дерево вывода, ветви
которого не длиннее, чем число нетерминалов грамматики G (этот аргумент
использовался в теореме 4.1).
Пусть A
1
, A
2
, ..., A
k
— те нетерминалы из словаря V
N
, из которых цепочка ε
может быть выведена, а B
1
, B
2
, ... , B
m
— те нетерминалы, из которых цепочка ε
не выводима. Мы построим новое множество правил P
1
следующим образом.
Если S
ε, то в P
1
включим правило S →ε. Никакие правила вида A →ε в
P
1
не включаются.
Если A → C
1
C
2
… C
r
∈P, r ≥ 1, то в P
1
включаются правила вида
A →α
1
α
2
... α
r
, где α
i
= C
i
, если C
i
∈V
T
∪ {B
1
, B
2
, ... , B
m
}, либо α
i
= C
i
или α
i
= ε,
если C
i
∈ {A
1
, A
2
, ..., A
k
}, однако не все α
i
= ε. Другими словами, в правой части
A-правила каждое вхождение A альтернативно либо подменяется на ε, либо
остаётся, как есть. Вхождения других символов не затрагиваются. При этом не
допускается, чтобы правая часть обратилась в ε.
Ясно, что новая грамматика G
1
=(V
N
, V
T
, P
1
, S) отличается от грамматики G
только набором правил, причём все они имеют требуемый вид.
I. Докажем, что L(G
1
) ⊆ L(G).
Пусть α
β и при этом применяется правило A → α
1
α
2
... α
r
∈P
1
. Его
применение эквивалентно применению правила A → C
1
C
2
... C
r
∈ P, из которого
оно было получено, и нескольких правил из множества правил P для выводов
C
i
ε, если α
i
= ε.
II. Докажем теперь, что L(G) ⊆ L(G
1
).
Индукцией по числу шагов l в выводе докажем, что если A
w и w ≠ε, то
A
w для A∈V
N
.
База. Пусть l =1.Очевидно, что вывод A
w есть также вывод A
w.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех выводов длиной l ≤ n (n ≥ 1) .
Индукционный
переход. Пусть A
w. Более детально этот вывод име-
ет следующий вид: A
C
1
C
2
... C
r
w
1
w
2
... w
r
, причём C
i
w
i
, l
i
≤ n.
*
G
⇒
*
G
⇒
*
G
⇒
1
*
G
⇒
1
G
⇒
1
G
⇒
G
n
⇒
G
⇒
1
G
n
+
⇒
G
l
⇒
G
⇒
i
G
l
⇒

Страницы