Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекция № 3 нов 2009.doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
536 Кб
Скачать
☆

2.2.3. Графы автоматов

Граф ЦА (ГА) - ориентированный граф, у которого в качестве вершин используются состояния, а в качестве дуг - переходы. В начале дуги фиксируется входной сигнал. Что касается выходного сигнала, то он для ЦА Мили ставится на конце дуги (рис.15), а для ЦА Мура внутри вершины (рис.16).

Таблица 12

СТП и В ЦА Мили

ДС

ПС

s1

s2

s3

s4

s1

x1

y4

x2

y3

s2

x2

y1

x1

y2

s3

x1

y4

x2

y3

s4

x2

y1

x1

y2

Таблица 13

СТП и В ЦА Мура

ДС

ПС

s1

s2

s3

s4

s1

x2

y2

x1

y3

s2

x1

y2

x2

y4

s3

x1

y1

x2

y2

s4

x1

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) при заходе в данное состояние должны быть одинаковые выходные сигналы.

Можно заметить, что если в ЦА Мили при заходе в каждое состояние имеются одинаковые выходные сигналы, то такой ЦА можно легко преобразовать в автомат Мура. Что касается преобразования автомата Мура в автомат Мили, то для этого достаточно перенести выходные сигналы из вершин на концы дуг.