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

UptoLike

ВУЗ: 

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

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

Рубрика: 

52
Очевидно, что все правила грамматики
G
′
при m ≤ 2 имеют такой вид,
какого требует нормальная форма Хомского. Остаётся преобразовать её
правила для m ≥ 3 к надлежащему виду. Модифицируем эту грамматику,
добавляя некоторые
дополнительные нетерминалы и заменяя некоторые
правила. Именно, для каждого правила вида A → B
1
B
2
...
B
m
∈ ,P
′
где m ≥ 3, мы
создаем новые нетерминалы и заменяем это правило множе-
ством правил вида
{A → B
1
D
1
, D
1
→ B
2
D
2
, ... , D
m – 3
→ B
m – 2
D
m – 2
, D
m – 2
→ B
m – 1
B
m
}.
Пусть
N
V
′′
— новый нетерминальный словарь, а
P
′
′
— новое множество
правил.
Рассмотрим контекстно-свободную грамматику
N
T
(,,,)GVVPS
′
′′′ ′′
=
.
Докажем, что она эквивалентна грамматике
.G
′
III. ( ) ( ).LG LG
′′′
⊆ Пусть S x. Один шаг этого вывода в грамматике ,G
′
на
котором используются правила вида A → a или
A → B
1
B
2
, является и шагом
вывода в грамматике
,G
′′
так как по построению эти правила также входят в
грамматику
.G
′′
Шаг
вывода в грамматике ,G
′
на котором используется правило A → B
1
B
2
...
B
m
,
m ≥ 3, равносилен последовательному применению правил
:G
′
′
A → B
1
D
1
, D
1
→ B
2
D
2
, ... , D
m – 3
→ B
m – 2
D
m – 2
, D
m – 2
→ B
m – 1
B
m
∈P
3
.
Поэтому имеем S
x.
IV.
() ().LG LG
′′ ′
⊆
Индукцией по длине вывода l покажем, что если для
любого A∈V
N
существует вывод A
x, x∈V
T
*
, то A
x.
База. Пусть l =1. Если
A
x,
A∈V
N
, x∈V
T
*
, то, согласно построению ,G
′
′
использованное правило A → x ∈
P
′
′
содержится также и во множестве правил
P
′
, так как в этом случае x∈V
T
, а тогда A
x.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех 1 ≤ l ≤ n (n ≥ 1).
Индукционный переход. Пусть A
x, где l = n +1. Этот вывод имеет
следующий вид: A
B
1
D
1
B
1
B
2
D
2
... B
1
B
2
... B
m –2
D
m –2
B
1
B
2
...
B
m
x.
Очевидно, что x = x
1
x
2
... x
m
, где B
i
x
i
, l
i
≤ n, i = 1, 2, ... , m.
По индукционной гипотезе B
i
x
i
. Следовательно, A
x.
В частности, при A = S получаем S x.
Утверждение IV доказано, а вместе с ним доказано равенство
() ( )LG LG
′′′
=
и сама теорема.
Пример 4.1. Рассмотрим грамматику G = ({S, A, B}, {a, b}, P, S), {a, b}, S),
в которой P =
{S → bA, S→ aB, A→ a, A→ aS, A→ bAA, B→ b, B→ bS,
B → aBB
}.
Построим эквивалентную грамматику в нормальной форме Хомского.
*
G
⇒
'
*
G
⇒
,,
N
12 2
... ,
m
D
DD V
−
∉
G
l
⇒
,,
*
G
⇒
'
G
⇒
,,
*
G
⇒
'
G
l
⇒
,,
G
⇒
,,
G
⇒
,,
G
⇒
,,
G
⇒
,,
G
⇒
,,
G
⇒
,,
i
G
l
⇒
,,
*
G
⇒
'
*
G
⇒
'
*
G
⇒
'

Страницы