Составители:
144
База. Пусть l = 1. Имеем (q, x, A, ε)
(q, ε, ε, y), где только одно движение
типа 1. Очевидно, что оно — первое движение, так как в исходной конфигу-
рации на вершине магазина находится A ∈N . Это движение не может привести к
появлению нетерминалов в магазинной цепочке из-за того, что они неизбежно
привели бы к другим движениям типа 1. Кроме того, магазинная цепочка,
замещающая A на вершине магазина, должна начинаться на x, так как только в
этом случае удастся продвинуться по входу x (в результате движений,
определенных в п.2). Наконец, магазинная цепочка должна заканчиваться на y
′
,
потому что только в этом случае на выходе может образоваться цепочка y (в
результате движений, определенных в п.3).
Поэтому фактически имеем
(q, x, A, ε) (q, x, xy’, ε) (q, ε, y’, ε) (q, ε, ε, y),
где первое движение обусловлено тем, что (q, xy’, ε)∈δ(q, ε, A), а это означает
существование правила A → x, y∈R. Два последних перехода выполнены согла-
сно пп.2, 3 построений. Воспользовавшись существующим правилом, немед-
ленно получаем вывод (A, A)
(x, y).
Индукционная гипотеза. Предположим, что вспомогательное
утверждение выполняется для всех l ≤ n (n ≥ 1).
Индукционный переход. Докажем утверждение для l = n + 1.
Пусть имеется переход (q, x, A, ε) (q, ε, ε, y), в котором ровно n +1
движение типа 1. Поскольку в исходной конфигурации на вершине магазина
A ∈N, то первое же движение — типа 1:
(q, x, A, ε) (q, x, x
0
y
0
′ B
1
x
1
y
1
′…B
m
x
m
y
m
′ , ε) (q, ε, ε, y). (1.5)
В конечной конфигурации магазин пуст. Цепочка x
0
∈Σ
*
, появившаяся в
верхней части магазина после первого движения, может быть удалена, только
если входная цепочка x начинается на x
0
. Поэтому далее последуют движения,
определяемые п.2, которые продвинут вход по x
0
и удалят такую же цепочку из
магазина. Далее ряд движений, определяемых п.3, удалит цепочку y
0
′
из
магазина, выдав на выход y
0
, и символ B
1
окажется на вершине магазина. К
моменту, когда вершина магазина опустится ниже этой позиции, будет
просканирована некоторая часть входа t
1
, следующая за цепочкой x
0
, а на
выходе образуется некоторая цепочка z
1
:
(q, x, A, ε) = (q,
x
0
t
1
x’, A, ε) (q, x
0
t
1
x’, x
0
y
0
’B
1
x
1
y
1
’… B
m
x
m
y
m
’, ε)
(q, t
1
x’, y
0
’B
1
x
1
y
1
’… B
m
x
m
y
m
’, ε) (q, t
1
x’, B
1
x
1
y
1
’… B
m
x
m
y
m
’,y
0
)
(q, x’, x
1
y
1
’… B
m
x
m
y
m
’, y
0
z
1
).
Далее мы можем повторить рассуждения, аналогичные рассуждениям
предыдущего абзаца, относя их к цепочкам x
i
∈Σ
*
, y
i
′
∈∆
′
(i = 1,2,…,m) и
B
j
∈N
( j = 2,…,m),
последовательно появляющимся в верхней части магазина в
результате серии движений, построенных в соответствии с п.2, затем с п.3, и
ряда движений, приводящих к понижению вершины магазина ниже позиции,
занимаемой
B
j
. Другими словами, детальный разбор возможных движений от
T
⇒
*
P
−
−
P
−−
*
P
−
−
*
P
−
−
*
P
−
−
*
P
−
−
P
−−
P
−
−
*
P
−−
*
P
−−
*
P
−
−
*
P
−−
*
P
−−
Страницы
- « первая
- ‹ предыдущая
- …
- 144
- 145
- 146
- 147
- 148
- …
- следующая ›
- последняя »
