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

UptoLike

ВУЗ: 

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

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

Рубрика: 

53
Во-первых, два правила, а именно: A → a и B → b, уже имеют требуемый вид.
Во-вторых, нет никаких цепных правил, так что мы можем начать с замены
терминалов в правых частях остальных правил на новые нетерминалы и
построения правил для них.
Правило S → bA заменяется двумя правилами S → С
1
A, С
1
→ b.
Аналогично правило S → aB заменяется правилами S → С
2
B, С
2
→ a.
Вместо A → aS вводятся правила A → С
2
S.
Правило A → bAA заменяется тремя новыми A → С
1
D
1
, D
1
→ AA.
Правило B → bS заменяется правилами B → С
1
S.
Правило B → aBB заменяется правилами B → С
2
D
2
, D
2
→ BB.
Итак, мы получили эквивалентную грамматику в НФХ:
G
1
= ({S, A, B, С
1
, С
2
, D
1
, D
2
}, {a, b}, P
1
, S), где
P
1
={S → С
1
A, S → С
2
B, A → С
2
S, A → С
1
D
1
, A → a,
B → С
1
S, B → С
2
D
2
, B → b, С
1
→ b, С
2
→ a, D
1
→ AA, D
2
→ BB}.
§ 4.3. Нормальная
форма Грейбах
Определение 4.4. Говорят, что контекстно-свободная грамматика
G =(V
N
, V
T
, P, S) представлена в нормальной форме Грейбах, если каждое её
правило имеет вид A → aα, где a∈V
T
, α∈V
N
*
.
Для доказательства того, что всякая контекстно-свободная грамматика
может быть приведена к нормальной форме Грейбах, нам потребуется
обосновать эквивалентность используемых при этом преобразований.
Лемма 4.2. Пусть G =(V
N
, V
T
, P, S) — контекстно-свободная грамматика,
A →α
1
Bα
2
∈P и {B →β
i
| B ∈V
N
, β
i
∈V
+
, i = 1, 2, ... , m} — множество всех B-
порождений, т.е. правил с нетерминалом B в левой части.
Пусть грамматика G
1
=(V
N
, V
T
, P
1
, S) получается из грамматики G отбра-
сыванием
правила A → α
1
Bα
2
и добавлением правил вида A → α
1
β
i
α
2
, i = 1, 2, ... , m.
Тогда L(G) = L(G
1
).
Доказательство.
I. L(G
1
) ⊆ L(G).
Пусть S
x, x ∈V
T
*
. Использование в этом выводе правила A →α
1
β
i
α
2
∈P
1
\ P
равносильно двум шагам вывода в грамматике G: A
α
1
Bα
2
α
1
β
i
α
2
. Шаги
вывода в грамматике G
1
, на которых используются другие правила из
множества правил P, являются шагами вывода в грамматике
G. Поэтому S
x.
II. L(G) ⊆ L(G
1
).
Пусть S
x. Если в этом выводе используется правило A →α
1
Bα
2
∈P \ P
1
,
то рано или поздно для замены B будет использовано правило вида B →β
i
∈P
.
Эти два шага вывода в грамматике G равносильны одному шагу вывода в грам-
матике
G
1
: A
α
1
β
i
α
2
.
Шаги, использующие другие правила из множества P,
являются шагами вывода в грамматике
G
1
. Поэтому S
x.
Что и требовалось доказать.
1
*
G
⇒
G
⇒
*
G
⇒
1
G
⇒
1
*
G
⇒
G
⇒
*
G
⇒

Страницы