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

UptoLike

ВУЗ: 

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

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

Рубрика: 

26
из которых может находиться один символ из Х. На ленте находится цепочка симво-
лов α∈ Х*. Ячейки слева и справа от цепочки не заполнены. Имеется некоторое ко-
нечное управляющее устройство с читающей головкой, которое может последова-
тельно считывать символы с ленты, передвигаясь слева направо. При этом устройство
может находиться в каком-либо одном состоянии из Q. Каждый раз, переходя к новой
ячейке, устройство переходит к новому состоянию в соответствии с функцией δ.
На рис. 2.1 изображен конечный автомат в начальном состоянии q
0
, считываю-
щий первый символ
1
i
х , входной цепочки α
i
. Стрелкой показано направление движе-
ния читающей головки. Отображение δ можно представить в виде совокупности так
называемых команд, которые обозначаются следующим образом:
(q, x) → q′,
где q, q′∈ Q; x = X.
Число команд конечно, левая часть команды (q, x) называется ситуацией авто-
мата, а правая q′ – есть состояние, в котором автомат будет находиться на следую-
щем шаге своей работы.
Графически команду удобно представлять в виде дуги графа, идущей из вер-
шины q в вершину q′ и помеченную символом х входного алфавита (рис. 2.2).
...
q
o
q х q′
Рис. 2.1. Интерпретация конечного автомата Рис. 2.2. Графическое
представление команды автомата
Полностью отображение δ изображают с помощью диаграммы состояний, т. е.
ориентированного графа, вершинам которого поставлены в соответствие символы Q,
а дугам – команды отображения δ.
Если автомат оказывается в ситуации (q
j
, x
i
), не являющейся левой частью ка-
кой-либо его команды, то он останавливается. Если управляющее устройство считает
все символы цепочки α, записанной на ленту, и при этом перейдет в состояние q
f
∈ F
(заключительное состояние), то говорят, что цепочка α допускается автоматом А
(автомат допускает цепочку α). Множество цепочек, допускаемых данным автоматом,
называют языком этого автомата.
Отображение δ можно представить и в виде функции:
δ (q, x) = q′,
где q, q′∈ Q; x ∈ X.
Эта функция интерпретируется так же, как и команда (q, x) → q′. Ее можно
распространить с одного входного символа на цепочку следующим образом:
δ(q, ε) = q, где ε – пустая цепочка;
δ(q, αx) = δ(δ(q, α), x), где х ∈ Х, α ∈ Х*.
Таким образом, можно сказать, что α допускается автоматом А, если
δ(q
0
, α) = q
f
, где q
f
∈ F,
1
i
х
2
i
х
3
i
х
k
i
х
i
α

Страницы