Введение в схемы, автоматы и алгоритмы
Выходом автомата должна быть последовательность
Выходом автомата должна быть последовательность (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.
| q0 | q0 | q0 | q0 | q1 | q0 |
| q1 | q0 | q1 | q1 | q1 | q0 |
| q0 | 0 | 1 | 1 | 0 | 0 |
| q1 | 1 | 0 | 0 | 1 | 1 |
Заметим, что после получения символа * автомат SUM переходит в начальное состояние q0 и готов выполнять сложение следующей пары чисел.
Рис. 4.1. Диаграмма автомата SUM
На диаграмме автомата у вершины q0 четыре петли, а у вершины q1 - три, объединены в одну с четырьмя и тремя метками, соответственно. Точно так же слиты два ребра из q1 в q0. Стрелкой указано начальное состояние.
