Составители:
60
Короче говоря, правила P
2
получаются из правил P
1
посредством
отбрасывания всех правил с нетерминалами B
j
в левых частях, а в оставшихся
правилах для нетерминалов A
i
все вхождения нетерминалов B
j
в правых частях
надо заменить какими-нибудь их терминальными порождениями. Поскольку
число таких терминальных порождений конечно, то и число получающихся
правил в P
2
тоже конечно.
Покажем теперь, что L(G
1
)=L(G
2
).
I. L(G
1
) ⊆ L(G
2
). Индукцией по длине вывода l докажем, что если A
i
w, то
A
i
w, w∈V
T
*
(i = 1, 2, ..., k).
База. Пусть l = 1 и пусть A
i
w. При этом применялось правило A
i
→ w∈P
1
,
где w∈V
T
*
. Но это же правило есть в P
2
по построению. Поэтому A
i
w.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех выводов длиной l ≤ n (n ≥ 1).
Индукционный переход. Рассмотрим вывод длиной l = n +1, причём
A
i
C
1
C
2
... C
r
w
1
w
2
... w
r
, где C
p
w
p
, w
p
∈V
T
*
, l
p
≤ n. На первом шаге приме-
няется правило A
i
→ C
1
C
2
... C
r
∈P
1
. Возьмем во множестве правил P
2
соответ-
ствующее правило, которое получается из данного заменой в нём всех
нетерминалов типа B на соответствующие w
p
, т.е. правило A
i
→ u
1
u
2
... u
r
∈P
2
, в
котором u
p
= w
p
, если C
p
∈V
T
∪ {B
1
, B
2
, ..., B
k
}, u
p
= C
p
, если C
p
∈{A
1
, A
2
, ..., A
k
},
p = 1,2,...,r.
Таким образом, имеем A
i
u
1
u
2
... u
r
, причём здесь все u
p
= w
p
, кроме тех u
p
,
которые равны C
p
∈{A
1
, A
2
, ... , A
k
}. Но для них u
p
= C
p
w
p
, l
p
≤ n, и по
индукционному предположению C
p
w
p
. Поэтому A
i
u
1
u
2
... u
r
w
1
w
2
... w
r
.
Итак, из A
i
w следует вывод A
i
w. Поскольку S∈{A
1
, A
2
, ... , A
k
}, то
L(G
1
) ⊆ L(G
2
).
II. L(G
2
) ⊆ L(G
1
). Пусть α β. Покажем, что α
β. Шаг вывода α
β
предполагает применение правила вида A
i
→ u
1
u
2
... u
r
∈P
2
. Его существование
обусловлено
существованием правила A
i
→ C
1
C
2
... C
r
∈P
1
, такого что либо C
i
= u
i
,
если u
i
∈V
T
, либо C
i
— нетерминал типа B и C
i
u
i
(i = 1, 2, ... , r).
Следовательно, A
i
C
1
C
2
... C
r
u
1
u
2
... u
r
.
Таким образом, применение одного правила A
i
→ u
1
u
2
...u
r
∈P
2
в выводе
α β равносильно применению нескольких правил из множества P
1
, позво-
ляющих в цепочке α заменить A
i
на u
1
u
2
... u
r
, что даёт β.
Итак, каждый шаг вывода терминальной цепочки в грамматике G
2
может
быть заменен несколькими шагами вывода в грамматике G
1
, т.е. L(G
2
) ⊆ L(G
1
).
Из рассуждений I и II следует, что L(G
1
)=L(G
2
).
Пример 4.3. Рассмотрим грамматику G
1
= ({S, A, B}, {a, b, c, d}, P
1
, S), где
P
1
= {S → ASB, S → AB, A → a, A → b, B → c, B → d}.
Легко видеть, что A порождает только цепочки a и b, а B порождает только
цепочки c и d. Однако, S порождает бесконечно много цепочек.
Правило
S → ASB заменяется правилами S → aSc, S → aSd, S → bSc,
S → bSd. Аналогично, правило S → AB заменяется правилами S → ac, S → ad,
S → bc, S → bd. Новая грамматика есть G
2
= ({S}, {a, b, c, d}, P
2
, S), где
P
2
= {S → aSc, S → aSd, S → bSc, S → bSd, S → ac, S → ad, S → bc, S → bd}.
1
G
l
⇒
2
*
G
⇒
1
G
⇒
2
G
⇒
2
G
⇒
2
G
⇒
1
G
n
⇒
1
p
G
l
⇒
1
p
G
l
⇒
2
*
G
⇒
2
*
G
⇒
2
*
G
⇒
1
*
G
⇒
1
*
G
⇒
2
G
⇒
2
G
⇒
1
G
⇒
2
G
⇒
1
G
⇒
1
*
G
⇒
1
*
G
⇒
Страницы
- « первая
- ‹ предыдущая
- …
- 59
- 60
- 61
- 62
- 63
- …
- следующая ›
- последняя »
