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

UptoLike

ВУЗ: 

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

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

Рубрика: 

143
На первом шаге данного вывода было применено правило
A → x
0
B
1
x
1
B
2
x
2
…B
m
x
m
, y
0
B
1
y
1
B
2
y
2
…B
m
y
m
∈R
и потому согласно п.1 построения имеем
(q,x
0
y
0
’B
1
x
1
y
1
’B
2
x
2
y
2
′…B
m
x
m
y
m
′, ε)∈δ(q, ε, A). (1.3)
Кроме того, согласно индукционной гипотезе из существования частичных
выводов (1.2), следует возможность перехода
(q,
t
i
,
B
i
,
ε)
(q, ε, ε, z
i
), i = 1, 2,…, m. (1.4)
Рассмотрим движения pdt P. Учитывая условия (1.1) и (1.3), можем написать:
(q, x, A, ε)=(q, x
0
t
1
x
1
t
2
x
2
…t
m
x
m
, A, ε)
(q, x
0
t
1
x
1
t
2
x
2
…t
m
x
m
, x
0
y
0
′ B
1
x
1
y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, ε).
Согласно п.2 построений имеем переход
(q, x
0
t
1
x
1
t
2
x
2
… t
m
x
m
, x
0
y
0
′ B
1
x
1
y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, ε)
(q, t
1
x
1
t
2
x
2
…t
m
x
m
, y
0
′ B
1
x
1
y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, ε);
согласно п.3 построений имеем переход
(q,t
1
x
1
t
2
x
2
…t
m
x
m
, y
0
′ B
1
x
1
y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, ε)
(q,t
1
x
1
…t
m
x
m
, B
1
x
1
y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, y
0
).
Учитывая существование перехода (1.4) для i = 1, получаем:
(q, t
1
x
1
t
2
x
2
…t
m
x
m
, B
1
x
1
y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, y
0
)
(q, x
1
t
2
x
2
…t
m
x
m
, x
1
y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, y
0
z
1
).
Далее рассуждения с использованием пп.2, 3 построений, а также
переходов (1.4) для i = 2, 3,…, m повторяются. В результате получаем последу-
ющие движения:
(q,x
1
t
2
x
2
…t
m
x
m
, x
1
y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, y
0
z
1
)
(q,t
2
x
2
…t
m
x
m
, y
1
′B
2
x
2
y
2
′…B
m
x
m
y
m
′, y
0
z
1
)
(q, t
2
x
2
…t
m
x
m
, B
2
x
2
y
2
′…B
m
x
m
y
m
′, y
0
z
1
y
1
) …
(q, t
m
x
m
, B
m
x
m
y
m
′, y
0
z
1
y
1
… z
m–1
y
m–1
)
(q, x
m
, x
m
y
m
′, y
0
z
1
y
1
… z
m–1
y
m–1
z
m
)
(q, ε, y
m
′, y
0
z
1
y
1
… z
m–1
y
m–1
z
m
)
(q, ε, ε, y
0
z
1
y
1
… z
m–1
y
m–1
z
m
y
m
)=(q, ε, ε, y).
В конце принято во внимание представление цепочки y согласно равенству (1.1).
Итак, вся последовательность движений может быть записана в виде
(q, x, A, ε) (q, ε, ε, y).
В частности, из доказанного вспомогательного утверждения при A = S
следует утверждение I.
II. Докажем теперь обратное утверждение:
если (q, x, S, ε) (q, ε, ε, y) , то (S, S)
(x, y).
Для этого индукцией по числу l движений типа 1, определённых согласно
п.1 построений, докажем более общее утверждение:
если для любого A∈N существует переход (q, x, A, ε) (q, ε, ε, y),
то (A ,A ) (x, y).
*
P
−
−
*
P
−
−
P
−
−
P
−
−
*
P
−−
*
P
−−
*
P
−
−
*
P
−
−
*
P
−−
*
P
−−
*
P
−−
*
P
−−
*
P
−−
*
P
−−
*
P
−−
*
P
−
−
*
P
−
−
*
P
−
−
*
P
−
−
*
P
−
−
*
P
−
−
*
P
−
−
*
T
⇒
*
P
−
−
*
P
−
−
*
T
⇒

Страницы