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

UptoLike

ВУЗ: 

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

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

Рубрика: 

152
II. Индукцией по длине ввода l = |π| покажем, что для любого A ∈N, если
(q, π, A, ε)
(q, ε, ε, y), то (A, A)
(x, y) при некотором x ∈Σ
*
.
База. Пусть l = 1, т.е. π = i и (q, i, A, ε)
(q, ε, ε, y). В общем случае этот
переход может происходить только следующим образом:
(q, i, A, ε)
(q, ε, y, ε)
(q, ε, ε, y).
Действительно, первое движение происходит согласно п.1, поскольку на
вершине магазина A ∈N. Других движений этого типа не существует, так как
каждое из них продвигается по входной цепочке на один символ. Возможные
же движения согласно п.2 предполагают нахождение в верхней части магазина
некоторой цепочки y ∈∆
*
.
Первое движение определяется значением δ(q, i, A) = (q, y, ε), предпола-
гающим существование правила вида A → x,y ∈R с номером i при некотором
x ∈Σ
*
. С его помощью немедленно получаем (A, A) (x, y).
Индукционная гипотеза. Предположим, что подобное утверждение
выполняется для всех вводов длиной l ≤ n (n ≥ 1).
Индукционный переход. Предположим, что утверждение выполняется
и для l = n + 1. Пусть (q, π, A, ε)
(q, ε, ε, y), где |π| = n + 1. В общем случае
эти движения могут происходить только следующим образом:
(q, π, A, ε) = (q, iπ’ , A, ε)
(q, π’, y
0
A
1
y
1
A
2
…A
m
y
m
, ε)
(q, π’, A
1
y
1
A
2
…A
m
y
m
, y
0
) = (q, π
1
π
2
…π
m
, A
1
y
1
A
2
…A
m
y
m
, y
0
)
(q, π
2
…π
m
, y
1
A
2
…A
m
y
m
, y
0
z
1
) (q, π
2
…π
m
, A
2
…A
m
y
m
, y
0
z
1
y
1
)
…
…
(q, ε, y
m
, y
0
z
1
y
1
…z
m
) (q, ε, ε, y
0
z
1
y
1
…z
m
y
m
) = (q, ε, ε, y).
Соответственно
π = iπ
1
π
2
…π
m
, y = y
0
z
1
y
1
z
2
…z
m
y
m
. (1.21)
Первое движение позволяет утверждать, что δ(q, i, A) = (q, y
0
A
1
y
1
A
2
…A
m
y
m
, ε),
и, следовательно, в схеме существует правило под номером i вида
A → x
0
A
1
x
1
A
2
…A
m
x
m
, y
0
A
1
y
1
A
2
…A
m
y
m
. (1.22)
Промежуточные движения вида (q, π
j
, A
j
, ε)
(q, ε, ε, z
j
), |π
j
|≤n, по
индукционному предположению гарантируют существование выводов вида
(A
j
, A
j
) (t
j
, z
j
) при некоторых t
j
∈∆
*
, j = 1, 2, …, m. (1.23)
Используя правило (1.22), выводы (1.23) и учитывая равенство (1.21),
можем построить вывод
(A, A) (x
0
A
1
x
1
A
2
…A
m
x
m
, y
0
A
1
y
1
A
2
…A
m
y
m
)
(x
0
t
1
x
1
t
2
…t
m
x
m
, y
0
z
1
y
1
z
2
…z
m
y
m
) = (x, y).
Здесь π’= π
1
π
2
…π
m
, iπ’= π, т. е. (A, A) (x, y).
Утверждение теоремы следует из рассуждений I и II при A = S.
*
P
−
−
*
P
−
−
*
P
−
−
*
P
−−
*
P
−−
*
P
−−
*
P
−−
*
P
−−
*
P
−
−
P
−−
*
P
−−
*
P
−
−
*
P
−−
P
−−
*
P
−
−
lm
π
⇒
lm
π
⇒
lm
i
⇒
lm
j
π
⇒
lm
i
⇒
lm
′
π
⇒
lm
′
π
⇒

Страницы