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

UptoLike

ВУЗ: 

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

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

Рубрика: 

116
Прежде всего отметим, что любой вывод и, в частности, вывод A
1
w
может начинаться только по правилам 1–5, дающим результат вида
A
1
q
0
[a
1
, a
1
][a
2
, a
2
] ... [a
k
, a
k
][ε, B]
m
.
Далее могут применяться правила 6 и 7, дающие в конце концов результат
вида
[a
1
, X
1
][a
2
, X
2
] ... q[a
j
, X
j
] ... [a
k+ m
, X
k+ m
],
где q∈F, после чего правила 8 дадут w = a
1
a
2
... a
k
.
Собственно, надо показать, что движения Tm T моделируются на участке
вывода
q
0
[a
1
, a
1
][a
2
, a
2
]...[a
k
, a
k
][ε, B]
m
[a
1
, Y
1
][a
2
, Y
2
] ... q[a
j
, Y
j
] ... [a
k + m
, Y
k + m
],
где q∈F.
Другими словами, если такой вывод имеет место, то существуют движения
Tm T вида
(q
0
, a
1
a
2
...a
k
, 1)
(q, Y
1
Y
2
...Y
k + m
, j).
Докажем это утверждение индукцией по длине вывода l.
База. Пусть l =0. Утверждение выполняется очевидным образом.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех l ≤ n (n ≥ 0).
Индукционный
переход. Пусть имеется вывод длиной l = n +1. В
общем случае имеем
q
0
[a
1
, a
1
][a
2
, a
2
]...[a
k
, a
k
][ε, B]
m
[a
1
, X
1
][a
2
, X
2
]...q
1
[a
j
1
, X
j
1
]...[a
k + m
, X
k + m
]
[a
1
, Y
1
][a
2
, Y
2
]...q[a
j
, Y
j
]...[a
k + m
, Y
k + m
],
где q∈F.
Согласно индукционной гипотезе существует переход
(q
0
, a
1
a
2
... a
k
, 1)
(q
1
, X
1
X
2
... X
k + m
, j
1
).
Ясно, что последний шаг вывода мог быть выполнен только посредством
правила вида 6 или 7. Если применялось правило вида 6, то j = j
1
+1; если
использовалось правило вида 7, то j = j
1
–1. Эти правила существуют благодаря
тому, что δ(q
1
, X
j
1
) = (q, Y
j
1
, D), где D = R, если j = j
1
+1, или D = L, если j = j
1
–1.
При этом X
i
= Y
i
для всех i ≠ j
1
. Благодаря этим значениям функции δ машина T
совершает ещё одно движение, переводящее её в принимающую
конфигурацию:
(q
0
, a
1
a
2
...a
k
, 1)
(q
1
, X
1
X
2
... X
k + m
, j
1
)
(q, Y
1
Y
2
...Y
k + m
, j),
где q∈F. Другими словами, показано, что w = a
1
a
2
... a
k
принимается Tm T.
Итак, если w∈L(G), то цепочка w принимается машиной T.
Теорема доказана полностью.
n
G
⇒
G
⇒
*
__
T
*
__
T
*
__
T
*
G
⇒
n
G
⇒
G
⇒
*
G
⇒
*
G
⇒
__
T

Страницы