Курсовая работа: Структурные автоматы

На структурном уровне каждая буква входного алфавита xХ, каждая буква выходного алфавита yY и каждая буква алфавита состояний аА кодируется двоичными векторами (двоичными наборами), число компонент которых определяется следующим образом:

K_вх >= int(log₂ |X|); K_вых >= int(log₂ |Y|); K_сост >=int(log₂ |A|);

где int - ближайшее большее целое число.

|Х|, |У|, |А| - мощность алфавита входного, выходного и состояний, соответственно. Мощностью алфавита называется количество различных символов входящих в этот алфавит.

Процесс замены буква алфавита (X, У, А) абстрактного автомата двоичными векторами носит название кодирования и описывается таблицами кодирования. Таблица кодирования имеем следующий вид: в левой части перечисляются все символы абстрактного алфавита, а в правой - соответствующие им двоичные векторы.

Рассмотрим пример.

Абстрактный автомат Мили задан таблицей переходов и выходов (табл. 2.). Выполнить кодирование алфавитов автомата.

Таблица2

А\ Х	x1	x2
a1	a2 /y1	a3 /y3
a2	a1 /y2	a2 /y1
a3	a2 /y2	a1 /y1

Выпишем алфавиты автомата и определим длины векторов кодов алфавитов:

X={x₁ ,x₂ }; K_вх >= int(log₂ |2|)=1,

Y={y₁ ,y₂ ,y₃ }; K_вых >= int(log₂ |3|)=2,

A={a1,a2,a3}; K_сост >= int(log₂ |3|)=2.

Заполним таблицы кодирования:

Таблица 3

x1	0
x2	1

Результирующая таблица - структурная таблица переходов и выходов автомата (табл. 6.) Получением структурной таблицы переходов -выходов автомата заканчивается этап кодирования.

Таблица 6.

А\ X	0	1
00	01/00	10/10
01	00/01	01/00
10	01/01	00/00