ВУЗ:
Составители:
Рубрика:
68
Порождение цепочек символов можно рассматривать как результат
работы некоторого гипотетического устройства, схема которого изобра-
жена на рис. 31.
Вдоль бесконечной (в одну или обе стороны) ленты, разделённой на
клетки, перемещается управляющая головка (УГ). Заданы внешний алфа-
вит M = { m
0
, m
1
, m
2
, ..., m
n
}, символы которого называются буквами,
внутренний алфавит S = {s
0
, s
1
, ..., s
r
}, символы которого называются со-
стояниями, и алфавит перемещений D = {П, Л, Н}. Все клетки ленты за-
полнены символами из алфавита M, по одному символу в каждой клетке.
Символ m
0
играет роль пустого символа (если в некоторой клетке стоит
символ m
0
, то «в клетке ничего не записано»). Предполагается, что вся
бесконечная лента всюду заполнена символами m
0
, за исключением тех
клеток, где записаны какие-либо другие символы из алфавита M.
Управляющая головка может находиться в тех или иных состояниях,
характеризуемых символами из множества S. Состояние s
0
− начальное
состояние УГ. Предполагается, что в конце работы машины управляю-
щая головка всегда переходит в некоторое конечное состояние s
z
. В про-
цессе работы машины УГ перемещается в дискретные такты времени
вдоль ленты. Перемещение управляющей головки в данный такт работы
происходит либо на одну клетку вправо (П), либо на одну клетку влево
(Л), либо может отсутствовать (Н).
В каждый такт работы машины УГ совершает следующие действия:
1) считывает символ m
i
, находящийся в клетке ленты, которую в этом
такте она «видит»; 2) в соответствии со считанным символом m
i
и своим
состоянием s
j
записывает символ m
k
в эту клетку; 3) движется или не
движется вдоль ленты; 4) переходит в следующее состояние s
p
.
Всю работу машины можно задать с помощью функциональной таб-
лицы Т, клетки которой заполнены тройками вида (m
k
, d
l
, s
p
), где d
l
∈ D –
символ, определяющий перемещение. Таким образом, функциональная
таблица определяет отображение множества M × S в множество M × D × S.
Содержательный смысл отображения (m
i
, s
j
) → (m
k
, d
l
, s
p
) состоит в том,
что, УГ, находясь в состоянии s
j
, считывает из видимой клетки ленты
символ m
i
; записывает в данную клетку ленты символ m
k
; производит
движение, определяемое символом d
l
, и переходит в состояние s
p
. Усло-
вимся считать, что функциональная таблица Т всегда устроена так, что
имеет место отображение (m
i
, s
z
) → (m
i
, Н, s
z
). Это означает, что машина
«выключена» и не работает.
m
1
m
1
m
1
m
1
m
2
m
0
m
0
m
1
m
0
m
0
m
2
УГ
Рис. 31
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
