2.2.3. Графы автоматов
Граф ЦА (ГА) - ориентированный граф, у которого в качестве вершин используются состояния, а в качестве дуг - переходы. В начале дуги фиксируется входной сигнал. Что касается выходного сигнала, то он для ЦА Мили ставится на конце дуги (рис.15), а для ЦА Мура внутри вершины (рис.16).
Таблица 12
СТП и В ЦА Мили
-
ДС
ПС
s1
s2
s3
s4
s1x1
y4
x2
y3
s2x2
y1
x1
y2
s3
x1
y4
x2
y3
s4x2
y1
x1
y2
Таблица 13
СТП и В ЦА Мура
-
ДС
ПС
s1
s2
s3
s4
s1x2
y2
x1
y3
s2x1
y2
x2
y4
s3
x1
y1
x2
y2
s4x1
y1
x2
y2
Таблица 14
ОМП
-
ДСПС
s1
y1
s2
y2
s3
y3
s4
y4
s1
х2
х1
s2
х1
х2
s3
х1
х2
s4
х1
х2
Р
ис.15.
ГА Мили Рис.16. ГА Мура
Условия корректности для ГА Мили можно сформулировать следующим образом:
1) при выходе из данного состояния должны использоваться разные входные сигналы;
2) при заходе в данные состояния допускаются одинаковые входные сигналы;
3) при заходе в данное состояние разрешаются одинаковые выходные сигналы.
Условия корректности для ГА Мура являются не сколько другими:
1) при выходе из данного состояния должны использоваться разные входные сигналы;
2) при заходе в данные состояния могут использоваться одинаковые входные сигналы;
3) при заходе в данное состояние должны быть одинаковые выходные сигналы.
Можно заметить, что если в ЦА Мили при заходе в каждое состояние имеются одинаковые выходные сигналы, то такой ЦА можно легко преобразовать в автомат Мура. Что касается преобразования автомата Мура в автомат Мили, то для этого достаточно перенести выходные сигналы из вершин на концы дуг.
