2. Анализ и синтез двоичных автоматов
Представления автоматов с помощью графа переходов и таблицы состояний задают численные характеристики структуры автомата и схему его функционирования. Однако для практической реализации такого автомата необходимо указать физическую структуру, которая могла бы выпол-нить данные преобразования. Здесь, как и при задании схемы функционирования, возникает проблема оптимиза-ции.
Во всех рассмотренных выше примерах обозначения входов, выходов и внутренних состояний автоматов не являются числами. Однако в реальных автоматах данные величины кодируют в виде чисел – обычно в двоичной системе счисления, поскольку выполнение преобразований информации проще осуществлять в числовой форме. Дан-ное преобразование входной и (при необходимости) выход-ной информации выполняют кодирующие устройства, стоящие на входе и выходе автомата.
2.1. Числовая форма задания автоматов. Двоичные автоматы
Определение. Представления таблицы состояний и графа переходов, в котором множества Q, Х, Z входов, вы-ходов и внутренних состояний автомата закодированы чис-лами в некоторой системе счисления, для краткости будем называть числовой формой их представления в отличие от нечисловой, в которой множества Q, Х, Z обозначены в иной форме. Если для кодирования использована двоичная система счисления, автомат будем называть двоичным.
302
Символу 0 обычно придают логическое значение ”ложь”, символу 1 - логическое значение ”истина”. Поэтому при двузначном кодировании элементов множеств Q, Х, Z описывать структуру и функционирование дискретных ав-томатов можно при помощи алгебры логики.
При использовании в кодировании множеств автомата Q, Х, Z трёх и более символов можно использовать методы многозначных логик.
Пример 1. Построить для автомата, заданного в Примере п. 1.1:
1) граф переходов и
2) таблицу состояний в двоичной форме.
Решение. Поскольку N=6, M=4, P=3, то для двоич-ного кодирования множеств входов X, выходов Z и внут-ренних состояний Q необходимо, соответственно,
n=]log 2 N[=]log 2 6[= 3,
m=]log 2 M[=]log 2 4[= 2,
p=]log 2 P[=]log 2 3[= 2
двоичных разрядов. При использовании кодов
X1000, X2001, X3010, X4011, X5100, X6101,
Z1 00, Z2 01, Z3 10, Z4 11,
Qож 00, Qв/A 01, Qв/В 10
некоторые из кодовых комбинаций (например 111, в коди-ровании входов X, 11 - для внутренних состояний Q) не ис-пользованы. При этом выходы Z и выходные значения внут-ренних состояний Q на соответствующих наборах (X,Q) не определены. Производя кодовые замены, получим двоичное представление графа переходов (Рис.5.12). Обозначая разря-ды для кодирования X через х1, х2, х3, Z - через z1,z2, Q - через q1, q2,, а неопределённые значения Z и Q вопроси-тельным знаком, построим также полную таблицу состоя-ний автомата в двоичной форме.
303
Рис.5.12
-
х1
х2
х3
q1(ti-1)
q2(ti-1)
z1
z2
q1(ti)
q2 (ti)
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
?
?
?
?
0
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
1
0
0
1
1
0
0
0
0
1
0
0
1
1
1
?
?
?
?
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
0
0
1
0
1
1
?
?
?
?
0
1
1
0
0
1
1
0
0
0
1
1
0
1
0
1
0
1
304
-
0
1
1
1
0
1
1
1
0
0
1
1
1
1
?
?
?
?
1
0
0
0
0
1
1
0
0
1
0
0
0
1
1
1
0
1
1
0
0
1
0
1
1
1
0
1
0
0
1
1
?
?
?
?
1
0
1
0
0
1
1
0
0
1
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
0
1
0
1
1
1
?
?
?
?
1
1
0
0
0
?
?
?
?
1
1
0
0
1
?
?
?
?
1
1
0
1
0
?
?
?
?
1
1
0
1
1
?
?
?
?
1
1
1
0
0
?
?
?
?
1
1
1
0
1
?
?
?
?
1
1
1
1
0
?
?
?
?
1
1
1
1
1
?
?
?
?
Двоичное представление графа переходов менее на-глядно, поэтому его есть смысл использовать только для ав-томатов с простой структурой.
Таблица состояний в числовом виде удобна для проек-тирования физической структуру автоматов.