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

UptoLike

ВУЗ: 

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

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

Рубрика: 

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

Страницы