Синтез цифровых автоматов. Захаров Н.Г - 29 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

28
V
2
= {А
1
, ..., А
k
, B} – конечное множество ленточных символов, которое в каче-
стве своего подмножества содержит входной алфавит;
Q = {q
0
, q
1
, ..., q
n-1
} – конечное множество состояний;
q
0
∈ Q – начальное состояние;
F ⊆ Q – множество заключительных состояний;
δ – функция, отображающая Q × V
2
в Q × (V
2
– {B} × {Л, П}.
(Л и П – специальные символы, указывающие на направление движения головки).
Отображение (функцию) δ удобно задавать совокупностью команд вида:
(q, A) → (q′, A′, Л) либо (q, A) → (q′, A′, П).
...
q
o
ВВВ
......
Рис. 2.4. Интерпретация машины Тьюринга
Ситуация машины Тьюринга Т – это тройка вида (q, β, i), где q ∈ Q;
β = A
1
, ..., A
n
– часть ленты, не содержащая символов В (непустая часть лен-
ты);
i = (0 ≤ i ≤ n+1) – расстояние ленточной (пишущей - читающей) головки от ле-
вого конца β; при i = 0 головка находится левее самого левого символа β, при
i = n+1 – правее самого правого.
Рассмотрим произвольную ситуацию машины Т:
(q, A
1
... A
i
.... A
n
, i), 1 ≤ i ≤ n.
Пусть среди команд отображения δ имеется следующая:
(q, A
i
) → (q′, X, Л).
При этом возможно следующее движение (или элементарное действие) маши-
ны Тьюринга: головка стирает символ А
i
, записывает вместо него символ Х и пере-
мещается на одну ячейку влево.
Между старой и вновь возникшей ситуациями в этом случае существует отно-
шение, которое записывается следующим образом:
(q, A
1
... A
i
.... A
n
, i) | (q′, A
1
... A
i-1
Х A
i+1
.... A
n
, i -1).
Символ | означает – «утверждается».
Аналогично для команды (q, A
i
) → (q′, X, П) движение машины Тьюринга за-
писывается как
(q, A
1
... A
i
.... A
n
, i) | (q′, A
1
... A
i-1
Х A
i+1
.... A
n
, i +1).
Кроме рассмотренной ситуации возможны и такие:
(q, A
1
... A
n
, 0);
(q, A
1
... A
n
, n+1).
К ним применимы команды вида (q, В) → (q′, X, Л) либо (q, В) → (q′, X, П).
Первая из этих команд меняет указанные ситуации соответственно следующим
образом:
1
i
а
2
i
а
3
i
а
n
i
а
i
α

Страницы