Теория алгоритмов и формальных языков. Мелихов А.Н - 32 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

в) аналогично работающая, но выполняющая сдвиг влево МТ l. Для МТ
r и МТ l соответственно имеем таблицы Тьюринга
10
100
rqxq
rqxq
n
M и
;
10
100
lxxq
lqxq
n
M
г) МТ, выполняющая трехкратный сдвиг ленты вправо и печать на ней
буквы х
0
:
21
101
10
100
rqxq
rqxq
rqxq
rqxq
n
n
M
M
;
403
4003
32
302
qxxq
qxxq
rqxq
rqxq
n
n
M
M
д) МТ К, переводящая начальную позицию
↑
ВВА в позицию
↑
ВВАВА .
1) q
0
Вrq
1
6) q
4
Вlq
5
11) q
5
В|q
7
16) q
2
Вlq
9
2) q
1
|rq
1
7) q
5
|lq
5
12) q
7
|rq
7
17) q
9
|lq
9
3) q
1
Вlq
2
8) q
5
Вlq
6
13) q
7
Вrq
8
4) q
2
|Вq
3
9) q
6
|lq
6
14) q
8
|rq
8
5) q
3
ВВq
4
10) q
6
В|q
7
15) q
8
В|q
2
Очевидно, что эта МТ копирует после пробела данное слово А.
Машины x
i
, r, l, К примем за элементарные машины. Тогда, например,
машину пункта г) можно собрать из трех машин r и машины х
0
.
Пусть М
1
, …, М
n
- некоторые элементарные МТ с общим алфавитом Х.
Диаграмма Тьюринга включает помимо символов элементарных машин
символ ⋅ (точка) и стрелки, взвешенные буквами алфавита Х. Причем символ
⋅ (точка) может встречаться в ДТ только один раз (он определяет начало
работы), а из любого символа может выходить не более одной стрелки,
взвешенной одной
и той же буквой. Теперь можно заменить таблицу
Тьюринга для МТ из примера г) диаграммой, показанной на рис. 2.2.

Страницы