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



             

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


Иногда пару функций ?,

называют программой автомата A и задают как список из m n команд вида qiaj
?(qi,aj) /
(qi,aj).

Другой удобный способ задания функций ? и

- табличный. Каждая из них определяется таблицей (матрицей) размера n ? m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита ?X. В первой из них на пересечении строки qi и столбца aj стоит состояние ?(qi,aj), а во второй - выходной символ
(qi,aj).

Еще один способ представления конечного автомата основан на использовании ориентированных размеченных графов.

Определение 4.2. Диаграмма автомата A = <?X, ?Y, Q, q0, ?,

> - это ориентированный (мульти) граф DA=(Q, E) с помеченными ребрами, в котором выделена вершина-начальное состояние q0 и из каждой вершины q
Q выходит |?X| ребер, помеченных парами символов a / b (a
?X, b
?Y). Таким образом, для каждой q
Q и каждого символа a
?X имеется единственное ребро с меткой a /
(q,a) из q в вершину q' =?(q,a).

Как автомат A перерабатывает входное слово x1x2 … xt? Он начинает работу в состоянии q(0)=q0. Затем, получив (прочитав) входной символ x1, переходит в состояние q(1)= ?(q0,x1) и выдает символ y(1)=

(q0,x1). Далее, получив x2 A переходит в состояние q(2)= ?(q(1),x2) и выдает символ y(2)=
(q(1),x2) и т.д. Таким образом, работа автомата, характеризуется последовательностью проходимых им состояний q(0), q(1), … , q(t), … и последовательностью выходных символов y(1), … , y(t), … . Они определяются следующими реккурентными соотношениями:

 \begin{array}{l} q(0)=q_0\\ q(1)= \Phi(q(0),x_1)\\ y(1)= \Psi(q_0,x_1)\\ \ldots\\ q(t+1)= \Phi(q(t),x_i)\\ y(t+1)= \Psi(q(t),x_i)\\ \ldots\\ \end{array}

Рассмотрим несколько примеров автоматов-преобразователей.

Пример 4.1. Сумматор последовательного действия

Мы уже строили схему из функциональных элементов SUMn, реализующую для фиксированного n суммирование двух n-разрядных двоичных чисел. Построим теперь конечный автомат SUM, который сможет складывать два двоичных числа произвольной разрядности. На вход этого автомата будут последовательно подаваться пары x(i)= (x1(i),x2(i)) соответствующих i-ых (1

i
r) разрядов двух двоичных чисел x1=x1(r) … x1(2) x1(1) и x2=x2(r) … x2(2) x2(1), а признаком завершения чисел будет служить символ x(r+1)= * (если одно из слагаемых короче другого, то будем считать, что недостающие разряды - нули).


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