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

UptoLike

ВУЗ: 

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

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

Рубрика: 

94
б
a) если δ(q, X) = ( p, Y, L), то (q, Xα, 1)
( p, Yα, 0);
b) если δ(q, B) = ( p, Y, R), то ( q, α, 0)
( p, Yα, 2);
c) если δ(q, B) = ( p, Y, L), то ( q, α, 0)
( p, Yα, 0).
Здесь B — пробел, а Y ≠ B. Начальной конфигурацией является (q
0
, w, 1). В
отличие от первоначальной модели нет никакого левого конца ленты, который
“выпадает”, так что она может двигаться влево сколь угодно далеко.
Степень, транзитивное замыкание и рефлексивно-транзитивное замыкание
отношения
определяются аналогично.
Теорема 6.1. Если язык L распознается машиной Тьюринга (Tm) с
бесконечной в обе стороны лентой, то он распознается Tm с полубесконечной
лентой.
Доказательство. Пусть T
2
= (Q
2
, Σ
2
, Γ
2
, δ
2
, q
2
, F
2
) — Tm с лентой,
бесконечной в обе стороны. Мы построим T
1
— машину Тьюринга,
моделирующую машину T
2
и имеющую ленту, которая бесконечна только
вправо. Эта лента имеет две дорожки. На верхней дорожке представляются
ячейки ленты машины T
2
, расположенные вправо от начального положения
головки, включая и саму ячейку, сканируемую вначале. На нижней — ячейки,
расположенные слева от начальной в порядке их удаления от начальной
позиции. Если мы припишем начальной ячейке машины T
2
номер 0, ячейкам,
которые справа, — номера 1, 2,..., а тем ячейкам, которые слева, припишем
номера –1, –2, ... , то связь между лентами машин T
2
(рис. 6.3, а) и T
1
(рис. 6.3,
б) может быть представлена так, как показано на этом рисунке.
… B A
0
A
1
A
2
A
3
A
4
…
A
0
A
1
A
2
A
3
A
4
…
¢
A
−1
A
−2
A
−3
A
−4
…
Рис. 6.3.
Первая непустая ячейка на ленте машины T
1
будет содержать на нижней
дорожке символ ¢, указывающий, что это — самая левая ячейка. Конечное
управление машины T
1
будет содержать информацию относительно того,
сканирует ли машина T
2
символ, находящийся на верхней или на нижней
дорожке.
Очевидно, что машина T
1
,
моделирующая машину T
2
,
может быть
построена. Когда машина T
2
находится
справа от начальной позиции она
неизменна, машина T
1
работает на верхней дорожке. Когда машина T
2
находится
слева от начальной позиции, машина T
1
работает на нижней дорожке,
двигаясь в направлении, противоположном направлению движения машины T
2
.
Входные символы машины T
1
— символы с пробелом на нижней дорожке и
входным символом машины T
2
на верхней дорожке. Такой символ
идентифицируется с соответствующим входным символом машины T
2
.
Теперь выполним формальное построение T
1
=(Q
1
, Σ
1
, Γ
1
, δ
1
, q
1
, F
1
).
__
T
a
q
2
__
T
__
T
__
T

Страницы