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

UptoLike

ВУЗ: 

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

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

Рубрика: 

122
Y – конечный выходной алфавит;
δ: Q x X → Q – функция следующего состояния;
λ: Q x X → Y – функция выхода.
Автоматы часто представляют в виде графов переходов (рис. 7.22). В графе пе-
реходов состояния представляются кружками, являющимися вершинами. Дуга из со-
стояния q
i
в q
j
, помеченная a / b означает, что находясь в состоянии q
i
, автомат при
входе а перейдет в состояние q
j
, выдавая при этом символ b. Формально можно запи-
сать: δ(q
i
, a) = q
j
и λ (q
i
, a) = b.
0/0 0/1
1/1
R/R
R/R 1/0
Рис. 7.22. Граф переходов для конечного автомата, вычисляющего
дополнение до двух двоичного числа
Этот автомат преобразует двоичное число, представленное последовательно-
стью бит, начиная с младшего, в дополнение до двух. В данном случае входной и вы-
ходной алфавиты состоят из трех символов: 0, 1, R. Автомат начинает работать в со-
стоянии q
1
. Символ сброса (R) означает конец (или начало) числа и возвращает авто-
мат в исходное состояние. Выход автомата для символа сброса является просто его
повторением.
При представлении конечного автомата сетью Петри следует обратить внима-
ние на связь между сетью Петри и внешними воздействиями. Моделирование взаи-
модействия с внешними воздействиями можно реализовать многими способами.
В данной задаче моделируем это взаимодействие с помощью специального множест-
ва позиций. Позициями будут представлены каждый входной и выходной символы.
Допустим, что в сеть Петри помещается фишка в позицию, соответствующую
входному символу, а затем фишка, появившаяся в позиции, соответствующей выход-
ному символу, то есть удаляется из сети (рис. 7.23).
В качестве альтернативного подхода к моделированию входов и выходов сети
могут быть использованы переходы. Для определения следующего входного символа
следует выбирать входной переход и запускать его. Сеть Петри ответит (в конце кон-
цов) запуском соответствующего перехода из множества выходных переходов, свя-
занного с соответствующим выходом. Затем будет запущен новый входной переход и
т. д. (рис. 7.24).
Задав представление позиций, соответствующих символам входа и выхода,
можно завершить построение модели системы конечных состояний. Текущее состоя-
ние отмечается фишкой, все остальные позиции пусты.
q
1
q
2

Страницы