Введение в схемы, автоматы и алгоритмы


             

Выходом автомата должна быть последовательность


Выходом автомата должна быть последовательность (r+1) двоичных разрядов суммы y = x1 + x2:



Таким образом, входной алфавит автомата: ?X ={ (00), (01), (10), (11), *}, а выходной алфавит: ?Y={ 0, 1}. Что нужно знать автомату SUM о первых i разрядах x1 и x2, чтобы получив их (i+1)-ые разряды (x1(i+1),x2(i+1)), верно определить выход y(i+1)? Ясно, что для этого достаточно знать, был ли перенос в i-ый разряд. Поэтому можно зафиксировать множество состояний Q = {q0, q1}, в котором q0 означает, что переноса не было, а q1 - что перенос был. Теперь легко построить таблицы, представляющие функции переходов и выходов автомата SUM.

?:Q\?X

(00)(01)(10)(11)*?:Q\?X(00)(01)(10)(11)*
q0q0q0q0q1q0
q1q0q1q1q1q0
q001100
q110011


Заметим, что после получения символа * автомат SUM переходит в начальное состояние q0 и готов выполнять сложение следующей пары чисел.


Рис. 4.1.  Диаграмма автомата SUM

На диаграмме автомата у вершины q0 четыре петли, а у вершины q1 - три, объединены в одну с четырьмя и тремя метками, соответственно. Точно так же слиты два ребра из q1 в q0. Стрелкой указано начальное состояние.


Содержание  Назад  Вперед