Составители:
51
Теперь
рассмотрим правило в P вида A → B
1
B
2
...
B
m
, где B
i
∈V, i =1, 2, ... , m,
m ≥ 2. Если B
i
∈V
T
, заменим его на новый нетерминал C
i
, C
i
∉V
N
, и создадим
новое
правило для него вида C
i
→ B
i
, которое имеет допустимую форму,
поскольку B
i
— терминал. Правило A → B
1
B
2
...
B
m
заменяется правилом A →
C
1
C
2
...
C
m
, где C
i
= B
i
, если B
i
∈V
N
.
Пусть пополненное множество нетерминалов —
N
V
′
, а пополненное множе-
ство правил —
.P
′
Рассмотрим грамматику Пока не все её правила удов-
летворяют нормальной форме Хомского (НФХ). Покажем, что она эквивалент-
на грамматике G.
I. Докажем, что
() ( ).LG LG
′
⊆
Пусть S x. Один шаг этого вывода в
грамматике G,
на котором используется правило A → B
1
B
2
...
B
m
∈P, равно-
силен в грамматике применению нового правила A → C
1
C
2
...C
m
∈
P
′
и не-
скольких правил вида C
i
→ B
i
∈ P
′
, о которых шла речь. Поэтому имеем
II. Докажем, что
() ().LG LG
′
⊆ Индукцией по длине вывода l покажем, что
если для любого A∈V
N
существует вывод где x∈V
T
*
, то
База. Пусть l = 1. Если
A∈V
N
, x∈V
T
*
, то согласно построению грамматики
G
′
использованное правило A → x ∈ P
′
имеется также и во множестве правил P.
Действительно,
| x | не может быть больше единицы, так как такое правило не
могло бы быть в множестве правил
.P
′
Следовательно, x — просто терминал,
и
A → x∈P, а тогда
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех 1
≤ l ≤ n (n ≥ 1).
Индукционный переход. Пусть где
l = n +1. Этот вывод имеет
вид:
где
m ≥ 2.
Очевидно, что x = x
1
x
2
... x
m
, причём l
i
≤ n, i = 1, 2,... , m.
Если то существует только одно правило из множества правил
P’,
которое определяет этот нетерминал:
C
i
→ a
i
для некоторого a
i
∈V
T
. В этом
случае
a
i
= x
i
. По построению правило A → C
1
C
2
...
C
m
∈P’, используемое на
первом шаге вывода, обязано своим происхождением правилу
A → B
1
B
2
... B
m
∈P, где B
i
= C
i
, если C
i
∈V
N
, и B
i
= a
i
, если
Для
C
i
∈V
N
мы имеем выводы
l
i
≤ n, и по индукционному предпо-
ложению существуют выводы
B
i
x
i
. Следовательно, A
x. При A = S имеем,
как частный случай,
x∈L(G).
Итак, мы доказали промежуточный результат: любой контекстно-свобод-
ный язык может быть порожден контекстно-свободной грамматикой, каждое
правило
которой имеет форму A → a или A → B
1
B
2
...
B
m
, где m ≥ 2, A, B
1
, B
2
, ...,
B
m
— нетерминалы, a — терминал.
*
G
⇒
*
G
⇒
*
G
⇒
*
.
G
Sx⇒
'
,
l
G
A
x⇒
'
*
.
G
A
x⇒
.
G
A
x⇒
,
l
G
Ax⇒
'
12
... ,
n
m
G
G
ACCC x⇒⇒
'
'
,
i
l
G
ii
Cx⇒
'
NN
\,
i
CVV
′
∈
NN
\.
i
CVV
′
∈
,
i
l
G
ii
Cx⇒
'
NT
(,,,).GVVPS
′
′
′
=
G
′
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
