ВУЗ:
Составители:
где 100001 - a, 10000001 - b, 1000000001 - c, 100000000001 - d.
Программа же будет представлена следующими строками:
1) 1000001 10000001 1000001 10000001 101
(q
0
b → q
0
b R)
2) 1000001 1000000001 1000001 1000000001 101
(q
0
c → q
0
c R)
3) 1000001 100001 100000001 1000000001 101
(q
0
a → q
1
c R)
3) 100000001 100000000001 10000000001 100000000001 10001
(q
1
d→q
2
dL).
Рассмотрим еще один пример. Пусть на ленту универсальной машины Тьюринга
поступает слово, составленное из букв английского алфавита. Задача машины Тьюринга -
переставлять местами буквы
n и o таким образом, чтобы сочетание on преобразовывалось в
no. Таким образом, после переработки входного слова в нем не должно остаться ни одного
буквосочетания
on.
Возьмем слово
mnonnop, которое должно преобразоваться универсальной машиной
Тьюринга в новое слово
mnnnoop.
Пусть внешний алфавит универсальной машины Тьюринга состоит из символов A =
{0,1}, а внутренний алфавит Q = {q
0
, q
1
, q
2
, q
3
, q
z
}, где q
z
- заключительное
состояние. Разбивка входных символов на кодовые группы и сопоставление кодовых групп
исходным символам внешнего и внутреннего алфавитов осуществляется согласно
приведенной выше таблице кодирования.
Тогда входное слово будет представлено следующим образом:
100001 10000001 1000000001 10000001 10000001 1000000001 100000000001,
где 100001 - m, 10000001 - n, 1000000001 - o, 100000000001 - p.
Ниже представлены команды универсальной машины Тьюринга, которые будут
выполняться при обработке и преобразовании исходного слова. Напротив каждой команды
приводится входное слово таким, какое оно есть в момент начала выполнения данной
команды. Символ, на который указывает головка машины Тьюринга, показан как прописная
буква.
q
0
m → q
0
m R M n o n n o p
q
0
n → q
0
n R m N o n n o p
q
0
o → q
1
o R m n O n n o p
q
1
n → q
2
o L m n o N n o p
q
2
o → q
0
n R m n O o n o p
q
0
o → q
1
o R m n n O n o p
q
1
n → q
2
o L m n n o N o p
q
2
o → q
0
n R m n n O o o p
q
0
o → q
1
o R m n n n O o p
q
1
o → q
0
o R m n n n o O p
q
0
p → q
z
p E m n n n o o P.
Программа же будет выглядеть так:
1000001 100001 1000001 100001 101
1000001 10000001 1000001 10000001 101
1000001 1000000001 100000001 1000000001 101
100000001 10000001 10000000001 1000000001 10001
10000000001 1000000001 1000001 10000001 101
1000001 1000000001 100000001 1000000001 101
где 100001 - a, 10000001 - b, 1000000001 - c, 100000000001 - d. Программа же будет представлена следующими строками: 1) 1000001 10000001 1000001 10000001 101 (q 0b → q 0 b R) 2) 1000001 1000000001 1000001 1000000001 101 (q 0c → q 0 c R) 3) 1000001 100001 100000001 1000000001 101 (q 0 a → q 1 c R) 3) 100000001 100000000001 10000000001 100000000001 10001 (q1d→q2dL). Рассмотрим еще один пример. Пусть на ленту универсальной машины Тьюринга поступает слово, составленное из букв английского алфавита. Задача машины Тьюринга - переставлять местами буквы n и o таким образом, чтобы сочетание on преобразовывалось в no. Таким образом, после переработки входного слова в нем не должно остаться ни одного буквосочетания on. Возьмем слово mnonnop, которое должно преобразоваться универсальной машиной Тьюринга в новое слово mnnnoop. Пусть внешний алфавит универсальной машины Тьюринга состоит из символов A = {0,1}, а внутренний алфавит Q = {q0, q1, q2, q3, qz }, где qz - заключительное состояние. Разбивка входных символов на кодовые группы и сопоставление кодовых групп исходным символам внешнего и внутреннего алфавитов осуществляется согласно приведенной выше таблице кодирования. Тогда входное слово будет представлено следующим образом: 100001 10000001 1000000001 10000001 10000001 1000000001 100000000001, где 100001 - m, 10000001 - n, 1000000001 - o, 100000000001 - p. Ниже представлены команды универсальной машины Тьюринга, которые будут выполняться при обработке и преобразовании исходного слова. Напротив каждой команды приводится входное слово таким, какое оно есть в момент начала выполнения данной команды. Символ, на который указывает головка машины Тьюринга, показан как прописная буква. q 0m → q 0m R Mnonnop q 0n → q 0n R mNonnop q 0o → q 1o R mnOnnop q 1n → q 2o L mnoNnop q 2o → q 0n R mnOonop q 0o → q 1o R mnnOnop q 1n → q 2o L mnnoNop q 2o → q 0n R mnnOoop q 0o → q 1o R mnnnOop q 1o → q 0o R mnnnoOp q 0p → q zp E m n n n o o P. Программа же будет выглядеть так: 1000001 100001 1000001 100001 101 1000001 10000001 1000001 10000001 101 1000001 1000000001 100000001 1000000001 101 100000001 10000001 10000000001 1000000001 10001 10000000001 1000000001 1000001 10000001 101 1000001 1000000001 100000001 1000000001 101
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »