Составители:
149
II. Докажем теперь обратное, т.е. если (x, y)∈τ
e
(P’), то (x, y)∈τ(P).
Пусть (x, y)∈τ(P’), т.е. (q
0
’, x, Z
0
’, ε)
(q
e
, ε, ε, y).
Рассмотрим подробнее его движения. Первое движение согласно п.1 имеет
вид: (q
0
’, x, Z
0
’, ε) (q
0
, x, Z
0
Z
0
’, ε).
Ясно, что для опустошения магазина pdt P’
должен оказаться в состоянии q
e
без этого ему не сбросить символ Z
0
’, находящийся на “дне” магазина. В
свою очередь, согласно п.2 pdt P’
достигает состояния q
e
только после того,
как, повторяя движения pdt P согласно п.3, он оказывается в состоянии q∈F. С
этого момента он не продвигается по входной цепочке, ничего не пишет на
выходную ленту и только стирает магазин. Это значит, что к моменту
достижения конечного состояния он уже прочитал всю свою входную цепочку
x и записал всю свою выходную цепочку y.
Дальнейшие движения pdt P’
имеют вид
(q
0
, x, Z
0
Z
0
’, ε) (q, ε, αZ
0
’, y) (q
e
, ε, ε, y), где q∈F, α∈Γ
*
.
Но на участке (q
0
, x, Z
0
Z
0
’, ε) (q, ε, αZ
0
’, y) pdt P’
лишь повторяет движе-
ния недетерминированного магазинного преобразователя P:
(q
0
, x, Z
0
, ε) (q, ε, α, y), q∈F, α∈Γ
*
.
Следовательно, (x, y) ∈τ(P).
Из рассуждений I и II следует справедливость леммы.
Лемма 1.4. Пусть P=(Q, Σ, Γ, ∆, δ, q
0
, Z
0
, F) — недетерминированный
магазинный преобразователь и τ = τ
e
(P). Существует недетерминированный
магазинный преобразователь P’, такой, что τ(P’)=τ.
Доказательство. Построим pdt P
’
, исходя из того соображения, что pdt P’
будет моделировать pdt P до тех пор, пока тот не примет свою входную
цепочку, опустошив магазин, а затем pdt P’
совершит ещё одно — ε-движение,
не записывающее ничего на выходную ленту, и перейдет в свое конечное
состояние, принимая ту же входную цепочку. Разумеется, надо позаботиться о
том, чтобы к этому моменту магазин не был пуст, иначе никакое дальнейшее
движение не будет возможно. Таким образом, pdt P’
будет принимать то же
самое множество входных цепочек при конечном состоянии, выдавая те же
выходные цепочки, что и pdt P.
Положим pdt P’=(Q’, Σ, Γ’, ∆, δ’, q
0
’, Z
0
’, F’). Здесь Q’ = Q ∪ {q
0
’ , q
f
},
q
0
’ , q
f
∉Q ; входной и выходной алфавиты — такие же, как у pdt P; Γ’ = Γ∪{Z
0
’},
Z
0
’∉Γ; F’ ={q
f
}.
Отображение
δ’ определяется следующим образом:
1. δ’(q
0
’ ,ε, Z
0
’) = {(q
0
, Z
0
Z
0
’, ε)} воспроизводит начальную конфигурацию
недетерминированного магазинного преобразователя P.
2. δ’(q,a, Z) содержит все элементы δ(q, a,Z) для q ∈Q , a ∈Σ∪{ε}, Z∈Γ, —
происходит собственно моделирование движений pdt P.
3. δ’(q,ε, Z
0
’)={(q
f
, α, ε)}, где α∈Γ
*
— произвольная магазинная цепочка,
— определяет переход в конечное состояние.
*
P
′
−
−
P
−−
'
*
P
′
−−
*
P
′
−
−
*
P
′
−
−
*
P
′
−
−
Страницы
- « первая
- ‹ предыдущая
- …
- 149
- 150
- 151
- 152
- 153
- …
- следующая ›
- последняя »
