Автомат Мили - модель управляющего автомата

Для формирования автоматной модели блок-схемы алгоритма необходимо:

1) все блоки "оператор" пометить символами y_i; это означает, что управляющий автомат воздействует на операционный автомат для исполнения y_i -ой операции; выход блока "оператор" (сигнал "1" для управляющего автомата) обуславливает переход к следующему шагу алгоритма и перевод управляющего автомата в новое состояние;

2) все блоки "предикат" пометить символами p_i; это означает, что операционный автомат проверяет p_i-ое условие; выход блока "предикат" формирует сигнал для управляющего автомата;

3) выход блока "начало" пометить символом q₀; это означает, что управляющий автомат до подачи входного сигнала (символ "1") находится в начальном состоянии;

4) выход блока "конец" пометить символом q_k=q₀; это означает, что после исполнения алгоритма управляющий автомат переводится в начальное состояние, на вход управляющего автомата подается сигнал об окончании работы алгоритма (символ "0");

5) безусловные переходы между блоками алгоритма формируют для управляющего автомата входной сигнал "1";

6) условные переходы между блоками алгоритма формируют для управляющего автомата входной сигнал в виде конъюнкции значений условий (p_i или p-_i) на маршруте от блока "оператор" или "начало" до очередного блока "оператор".

Пусть даны блок-схемы некоторых алгоритмов (см. рис.2.19).

Рис. 2.19 Разметка блок-схем алгоритмов для автомата Мили.

Разметка блок-схемы согласно правилам позволяет выделить множества входных сигналов для управляющего автомата и его внутренних состояний:

a) X={0;1;p;p-}; Q={q₀;q₁};

b) X={0;1;p;p-}; Q={q₀;q₁;q₂};

c) X={0;1;p-₁;p₁.p₂;p₁.p-₂}; Q={q₀;q₁};

d) X={0;1;p₁;p-₁.p₂;p-₁.p-₂}; Q={q₀;q₁;q₂}.

Таблицы поведения управляющих автоматов, реализующих указанные алгоритмы, приведены в таблице 2.18, а графы на рис. 2.20.

Таблица 2.18

Рис. 2.20 Графы автоматов Мили, моделирующих алгоритмы.

Пример 2.1. Пусть дано дискретное устройство, формирующее два множества согласно алгоритму, приведенному на рис. 2.21.

Рис. 2.21 Разметка блок-схемы для автомата Мили.

Разметка блок-схемы согласно правилам позволяет выделить множества входных сигналов для управляющего автомата и его внутренних состояний:

X={0;1; p-; p₁.p₂; p₁.p-₂; (p₃.p₄Úp-₃.p₅); (p₃.p-₄Úp-₃.p-₅)};

Q=(q₀; q₁; q₂; q₃; q₄}.

Введем обозначения k₁=(p₃.p₄Úp-₃.p₅), k₂=(p₃.p-₄Úp-₃.p-₅).

Таблица поведения управляющего автомата приведена в таблице 2.19, а граф - на рис. 2.22.

Таблица 2.19

Рис. 2.22 Граф управляющего автомата дискретного устройства (автомат Мили).

Таблица поведения автомата Мили соответствует недетерминированному автомату, что несколько усложняет процедуру минимизации числа внутренних состояний. Однако, если применить алгоритм минимизации частично опредленного автомата, то можно получить автомат, имеющий только три внутренних состояния (см. таблицу 2.20 и рис.2.23).

Таблица 2.20

где q^* замещает три состояния: q₁;q₂;q₃.

Рис.2.23 Минимизированный автомат Мили.

Дата добавления: 2015-07-26; просмотров: 212; Нарушение авторских прав

Мы поможем в написании ваших работ!