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

UptoLike

ВУЗ: 

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

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

Рубрика: 

31
Конечное управляющее устройство (УУ) снабжается дополнительной управ-
ляющей головкой, всегда указывающей на верхнюю ячейку магазинной памяти: за
один такт работы автомата управляющая головка может произвести следующие дви-
жения:
1) стереть символ из верхней ячейки (при этом все символы, находящиеся на
рабочей ленте, перемещаются на одну ячейку вверх);
2) стереть символ из верхней ячейки и записать на рабочую ленту непустую
цепочку символов (при этом содержимое рабочей ленты сдвигается вниз ровно на-
столько, какова длина записываемой цепочки).
Таким образом, устройство магазинной памяти можно сравнить с устройством
магазина боевого автомата; когда в него вкладывается патрон, те, которые уже были
внутри, проталкиваются вниз; достать можно только патрон, вложенный последним.
Формально детерминированный магазинный автомат определяется как сле-
дующая совокупность объектов:
М = (V, Q, V
м
, δ, q
0
, z
0
, F),
где V, Q, q
0
∈ Q, F – определяются также, как и для конечного автомата;
V
м
= {z
0
, z
1
, ..., z
p-1
} – алфавит магазинных символов автомата;
δ – функция, отображающая множество Q х (V ∪ {ε}) x V
м
в множество Q x
V
м
, где ε – пустая цепочка;
z
0
∈ V
м
– так называемый граничный маркер, т. е. символ, первым появляю-
щийся в магазинной памяти.
Недетерминированный магазинный автомат отличается от детерминиро-
ванного только тем, что значениями функции переходов являются не состояния, а
множества состояний, т. е. функция δ отображает множество Q х (V ∪ {ε}) x V
м
в
множество конечных подмножеств Q x V
м
.
Как и в случае конечных автоматов, преобразователи с магазинной памятью
отличаются от автоматов с магазинной памятью наличием выходной ленты. Далее
будем рассматривать только недетерминированные магазинные автоматы.
Рассмотрим интерпретацию функции δ для такого автомата. Эту функцию
можно представить совокупностью команд вида:
(q, a, z) → (q
1
, γ
1
), ..., (q
m
, γ
m
),
где q, q
1
, ..., q
m
∈ Q, a ∈ V, z ∈V
м
, γ
1
, ..., γ
m
∈V
м
*.
При этом считается, что если на входе читающей головки автомата находится
символ а, автомат находится в состоянии q, а верхний символ рабочей ленты z, то ав-
томат может перейти к состоянию q
i
, если записать на рабочую ленту цепочку
γ
i
(1 ≤ i ≤ m) вместо символа z и передвинуть входную головку на один символ
вправо.
Крайний левый символ γ
i
должен при этом оказаться в верхней ячейке магази-
на. Команда (q, ε , z) → (q
1
, γ
1
), ..., (q
m
, γ
m
) означает, что независимо от входного сим-
вола и, не передвигая входной головки, автомат перейдет в состояние q
i
, заменив
символ z магазина на цепочку γ
i
(1 ≤ i ≤ m).
Ситуацией магазинного автомата называется пара (q, γ), где q ∈ Q, γ
∈V
м
* .
Между ситуациями магазинного автомата (q, γ) и (q′, γ′) устанавливается отно-
шение, обозначаемое символом , если среди команд найдется такая, что (q, ε , z) →

Страницы