Переработка информации с помощью конечных автоматов - часть 3

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

$\begin{tabular}{ccccc} & x_1(r) & \ldots & x_1(2)& x_1(1)\\ +& x_2(r) & \ldots & x_2(2)& x_2(1)\\ \hline y(r+1) & y(r) & \ldots & y(2)& y(1) \end{tabular}$

Таким образом, входной алфавит автомата: ?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)*

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. Стрелкой указано начальное состояние.

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