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

UptoLike

ВУЗ: 

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

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

Рубрика: 

95
Положим Q
1
={q
1
} ∪ {[q, D] | q∈Q
2
, D∈{U, L }}. Здесь вторая компонента
состояния указывает, работает ли машина T
1
на верхней или нижней дорожке
9
.
Ленточные символы Γ
1
= {[X, Y] | X∈Γ
2
,
Y∈ Γ
2
∪ {¢}, ¢ ∉Γ
2
}. Если B —
пробел на ленте машины T
2
, то [B, B] — пробел на ленте машины T
1
.
Входные символы Σ
1
= {[a, B] | a ∈Σ
2
}. Мы идентифицируем a с [a, B].
Конечные состояния F
1
= {[q, D] | q ∈F
2
, D ∈{U, L}}.
Функцию δ
1
определим следующим образом:
1. Для любого a ∈Σ
2
полагаем
δ
1
(q
1
, [a, B]) = ([q, U ], [X, ¢], R), если δ
2
(q
2
, a) = (q, X, R).
Если первое движение машины T
2
происходит вправо, то машина T
1
печатает ¢ на нижней дорожке, чтобы не потерять начальную позицию T
2
,
устанавливает вторую компоненту состояния на U и двигается вправо. Первая
компонента состояния машины T
1
фиксирует состояние управления машины T
2
.
При этом машина T
1
печатает символ X на верхней дорожке, если машина T
2
печатает его на своей ленте.
2. Для любого a∈Σ
2
полагаем
δ
1
(q
1
, [a, B]) = ([q, L], [X, ¢], R), если δ
2
(q
2
, a) = (q, X, L).
Если первое движение машины T
2
происходит влево, то машина T
1
печатает
¢ на нижней дорожке, не потерять начальную позицию T
2
, устанавливает
вторую компоненту состояния на L и двигается вправо. Первая компонента
состояния T
1
фиксирует состояние T
2
. При этом машина T
1
печатает символ X на
верхней дорожке, если машина T
2
печатает его на своей ленте.
3. Для любого [X, Y ] ∈ Γ
1
с Y ≠ ¢ и D∈{L, R} полагаем
δ
1
([q, U ], [X, Y ]) = ([ p, U ], [Z, Y ], D), если δ
2
(q, X ) = ( p, Z, D).
Машина T
1
моделирует машину T
2
на своей верхней дорожке. Направление
движения головки машины T
1
противоположно направлению движения
машины T
2
.
4. Для любого [X, Y ] ∈Γ
1
с Y ≠ ¢ и D∈{L, R} полагаем
δ
1
([q, L], [X, Y ]) = ([ p, L], [X, Z ], D), если δ
2
(q, Y) = (p, Z,
D
).
Если D = L, то
D = R. Если D = R, то D = L.
Машина T
1
моделирует машину T
2
на своей нижней дорожке. Направление
движения головки машины T
1
противоположно направлению движения
машины T
2
.
5. Полагаем, что
δ
1
([q, U ], [X, ¢]) = δ
1
([q, L], [X, ¢]) = ([p, E ], [Y, ¢], R), если δ
2
(q, X) = (p, Y, D);
E = U, если D = R; E = L, если D = L.
Машина T
1
моделирует движение машины T
2
на ячейке, сканированной
машиной T
2
в самом начале. Затем машина T
1
работает на верхней или нижней
дорожке в зависимости от направления, в котором движется машина T
2
. В этой
позиции машина T
1
будет всегда двигаться вправо.
9
Здесь символ L (lower) обозначает нижнюю дорожку и его не следует путать с L в составе
значений
δ, где L обозначает left (влево). Символ U (upper) обозначает верхнюю дорожку.

Страницы