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



             

Переработка информации с помощью конечных автоматов - часть 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)*
q0q0q0q0q1q0
q1q0q1q1q1q0
q001100
q110011

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

 Диаграмма автомата SUM

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

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




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