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

UptoLike

ВУЗ: 

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

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

Рубрика: 

79
[qAp]
x
тогда и только тогда, когда (q, x, A)
(p, ε, ε).
В частности, при q = q
0
и A = Z
0
[q
0
Z
0
p]
x тогда и только тогда, когда (q
0
, x, Z
0
)
(p,
ε, ε).
Остаётся вспомнить, что существуют правила вида S → [ q
0
Z
0
q] для любых
q∈Q, в частности для q = p; тогда, пристраивая новое начало к выводу,
получаем справедливость следующего утверждения: S
[q
0
Z
0
p]
x
тогда и
только тогда, когда (q
0
, x, Z
0
)
(p, ε, ε), или, что то же самое, L(G)=N(M).
Что и требовалось доказать.
Теоремы 5.1, 5.2 и 5.3 можно подытожить: следующие три утверждения
являются эквивалентными:
1) L — cfl;
2) L = N(M
1
) для некоторого pda M
1
;
3) L = T(M
2
) для некоторого pda M
2
.
Пример 5.3. Пусть pda M = ({q
0
, q
1
}, {0, 1}, {X, Z
0
}, δ, q
0
, Z
0 ,
∅),
где
δ = {(1) δ(q
0
, 0, Z
0
)={(q
0
, XZ
0
)}, (4) δ(q
1
, 1, X )={(q
1
, ε)},
(2)
δ(q
0
, 0, X )={(q
0
, XX)}, (5) δ(q
1
, ε, X )={(q
1
, ε)},
(3) δ(q
0
, 1, X )={(q
1
, ε)}, (6) δ(q
1
, ε, Z
0
)={(q
1
, ε)}}.
Нетрудно сообразить, что N(M) = {0
n
1
m
n ≥ m}.
Построим cfg G = (V
N
, V
T
, P, S), порождающую язык N(M), положив
V
N
= {S, [q
0
Z
0
q
0
], [q
0
Z
0
q
1
], [q
1
Z
0
q
0
], [q
1
Z
0
q
1
], [q
0
Xq
0
], [q
0
Xq
1
], [q
1
Xq
0
], [q
1
Xq
1
]},
V
T
= {0, 1}.
Для экономии времени начнём движений (3−6), дающих правила
грамматики для нетерминалов, заведомо продуктивных.
Движение (3) δ(q
0
, 1, X) = {(q
1
, ε)} даёт:
[q
0
X q
1
] → 1
Движение (4) δ(q
1
, 1, X) = {(q
1
, ε)} даёт:
[q
1
X q
1
] → 1
Движение (5) δ(q
1
, ε, X) = {(q
1
, ε)} даёт:
[q
1
X q
1
] → ε
Движение (6) δ(q
1
, ε, Z) = {(q
1
, ε)} даёт:
[q
1
Z q
1
] → ε
Итак, в множество продуктивных нетерминалов R включены: [q
0
Xq
1
],
[q
1
Xq
1
], [q
1
Z q
1
].
Далее мы построим правила для S:
(0.1) S → [q
0
Zq
0
] и (0.2) S → [q
0
Zq
1
].
Затем, исходя из движения (1), мы добавим правила для нетерминала
[q
0
Zq
0
]:
(1.1) [q
0
Zq
0
] → 0[q
0
Xq
0
][q
0
Zq
0
],
(1.2) [q
0
Zq
0
] → 0[q
0
Xq
1
][q
1
Zq
0
].
Поскольку только [q
0
Xq
1
], [q
1
Xq
1
], [q
1
Zq
1
] ― продуктивные, то оба правила
(1.1−1.2) , а также (0.1), излишни.
*
G
⇒
G
⇒
*
G
⇒
*
__
M
*
__
M
*
__
M
*
G
⇒

Страницы