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

UptoLike

ВУЗ: 

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

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

Рубрика: 

74
Выше этого маркера при последующих движениях, повторяющих движения
pda M, всегда будут находиться только магазинные символы автомата M. Это
обеспечивается правилом 2. Когда же будет воспроизведено последнее
движение pda M, опустошающее его магазин, на вершине магазина автомата M
’
появится маркер дна. В этот момент pda M
’
посредством правила 3
переводится
в конечное состояние, тем самым сигнализируя приём входной цепочки.
Заметим, что движение по правилу 3 стирает символ магазина X, но могло бы
записать вместо него любую магазинную цепочку.
I.1. Докажем, сначала, что если x∈N(M), то x∈T(M
’
).
Пусть
x∈N(M), т.е. (q
0
, x, Z
0
)
*
__
M
(q, ε, ε). Посмотрим, какие движения будет
совершать автомат M
’
, имея на входе цепочку символов x.
Согласно правилу 1 (
0
q
'
, x, X) (q
0
, x, Z
0
X). Далее согласно правилу 2 pda
M
’
, повторяя движения автомата M,
осуществляет переход (q
0
, x, Z
0
X) (q, ε, X).
Наконец, по правилу 3 имеем последнее движение: (q, ε, X) (q
f
, ε, ε). Таким
образом, x∈T(M
’
).
I.2. Теперь докажем, что если x ∈T(M
’
), то x∈N(M).
Пусть
x∈T(M
’
), т.е. (
0
q
'
, x, X)
*
__
M
′
(q
f
, ε, γ) для некоторой цепочки γ∈(Γ∪{X})
*
,
причём по построению автомата M
’
γ = ε. Выделив здесь первый шаг явным
образом, имеем (
0
q
'
, x, X) (q
0
, x, Z
0
X)
*
__
M
′
(q
f
, ε, ε). Заключительная конфигу-
рация (q
f
, ε, ε) достижима лишь посредством ε-движения благодаря правилу 3 в
случае, когда на вершине магазина находится X. Следовательно, предпоследняя
конфигурация должна иметь вид (q
0
, ε, X).
Итак, все движения выстраиваются в следующую последовательность
конфигураций:
(
0
q
'
, x, X)
*
__
M
′
(q
0
, x, Z
0
X)
*
__
M
′
(q, ε, X) (q
f
, ε, ε).
Но на главном участке (q
0
, x, Z
0
X)
(q, ε, X) автомат M
’
просто повторяет
движения автомата M. Поэтому (q
0
, x, Z
0
)
*
__
M
(q, ε, ε) и x∈N(M).
Из рассуждений, проведенных в пп.I.1 и I.2 следует, что T(M
’
)=N(M).
II.
Достаточность. Пусть M = (Q, Σ, Γ, δ, q
0
, Z
0
, F) — недетерминирован-
ный
pda, такой, что L = T(M). Положим
M
’
= (Q ∪ {
0
q
'
, q
e
}, Σ, Γ∪{X}, δ′,
0
q
'
, X, ∅),
где δ′
определяется следующим образом:
1) δ′
(
0
q
'
, ε, X) = {(q
0
, Z
0
X)};
2) δ′
(q, a, Z) = δ(q, a, Z) для всех q∈Q, a∈ (Σ∪{ε}) и Z∈Γ;
3) δ′
(q, ε, Z) = {(q
e
, ε)} для всех q∈F и Z∈Γ∪{X};
4) δ′
(q
e
, ε, Z) = {(q
e
, ε)} для всех Z∈Γ∪{X}.
Правило 1 воспроизводит начальную конфигурацию автомата M. При этом
начальный символ магазина X остаётся в качестве своеобразного маркера дна
__
M
′
__
M
′
__
M
′
__
M
′
*
__
M
′
*
__
M
′

Страницы