Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
Автомат Мура - модель управляющего автомата
Для формирования автоматной модели необходимо:
1) все блоки "оператор" пометить символами yi и qi; это означает, что управляющий автомат воздействует на операционный автомат для исполнения yi -ой операции и одновременно переходит в qi-ое состояние; выход блока "оператор" (сигнал "1" для управляющего автомата) обуславливает переход к следующему шагу алгоритма;
2) все блоки "предикат" пометить символами pi; это означает, что операционный автомат проверяет pi -ое условие; выход блока "предикат" формирует сигнал для управляющего автомата;
3) блок "начало" пометить символом q0; это означает, что управляющий автомат до подачи входного сигнала (символ "1") находится в начальном состоянии;
4) блок "конец" пометить символом qk=q0; это означает, что после исполнения алгоритма управляющий автомат переводится в начальное состояние, на вход управляющего автомата не подается входной сигнал (символ "0");
5) безусловные переходы между блоками алгоритма формируют для управляющего автомата входной сигнал "1";
6) условные переходы между блоками алгоритма формируют для управляющего автомата входной сигнал в виде конъюнкции значений условий (pi или p-i) на маршруте от блока "оператор" или "начало" до очередного блока "оператор".
Пусть даны блок-схемы некоторых алгоритмов (см. рис.2.24).
Рис. 2.24 Разметка блок-схем алгоритмов для автомата Мура.
Разметка блок-схемы согласно правилам позволяет выделить множества входных сигналов для управляющего автомата и его внутренних состояний:
a) X={0;1;p;p-}; Q={q0;q1};
b) X={0;1;p;p-}; Q={q0;q1;q2};
c) X={0;1;p-1;p1.p2;p1.p-2}; Q={q0;q1};
d) X={0;1;p1;p-1.p2;p-1.p-2}; Q={q0;q1;q2}.
Таблицы поведения управляющих автоматов, реализующих указанные алгоритмы, приведены в таблице 2.21, а графы на рис. 2.25.
Таблица 2.21
| a) | b) | |||||||||||||
| текущее состояние (выход) | входные символы | текущее состояние (выход) | входные символы | |||||||||||
| p | p- | p | p- | |||||||||||
| q0( 0 ) | q1 | — | — | q0( 0 ) | — | q1 | q2 | |||||||
| q1(y1) | — | q0 | q1 | q1(y1) | q0 | — | — | |||||||
| q2(y2) | q0 | — | — | |||||||||||
| c) | d) | |||||||||||||
| текущее состояние (выход) | входные символы | текущее состояние (выход) | входные символы | |||||||||||
| p-1 | p1.p2 | p1.p-2 | p1 | p-1.p2 | p-1.p-2 | |||||||||
| q0( 0 ) | q1 | — | — | — | q0( 0 ) | — | q1 | q2 | q0 | |||||
| q1(y1) | — | q1 | q0 | q1 | q1(y1) | q0 | — | — | — | |||||
| q2(y2) | q0 | — | — | — | ||||||||||
Рис. 2.25 Графы автоматов Мура, моделирующих алгоритмы.
Пример 2.2. Пусть дано дискретное устройство, формирующее два множенства согласно алгоритму, приведенному на рис. 2.26.
Рис. 2.26 Разметка блок-схемы алгоритма для автомата Мура.
Разметка блок-схемы согласно правилам позволяет выделить множества входных сигналов для управляющего автомата и его внутренних состояний:
X={0;1; p-; p1.p2; p1.p-2; (p3.p4Úp-3.p5); (p3.p-4Úp-3.p-5)};
Q={q0; q1; q2; q3; q4}.
Введем обозначения k1=(p3.p4Úp-3.p5), k2=(p3.p-4Úp-3.p-5).
Таблицы поведения управляющего автомата приведена в таблице 2.22, а граф - на рис. 2.27.
Таблица 2.22
| текущие состояния (выход) | входные символы | |||||
| p-1 | p1.p2 | p1.p-2 | k1 | k2 | ||
| q0(0) | q1 | — | — | — | — | — |
| q1(y1) | — | q1 | q2 | q4 | — | — |
| q2(y2) | q3 | — | — | — | — | — |
| q3(y3) | — | — | — | — | q0 | q2 |
| q4(y4) | q0 | — | — | — | — | — |
Рис. 2.27. Граф управляющего автомата дискретного устройства
(автомат Мура).
Поведение автомата Мура также соответствует поведению недетерминированного автомата.
Контрольные вопросы и задачи.
1) Каковы основные правила разметки блок-схемы алгоритма для моделирования автоматом Мили?
2) Каковы основные правила разметки блок-схемы алгоритма для моделирования автоматом Мура?
3) Почему нельзя выполнить процедуру минимизации для автомата Мура?
4) Выполнить разметку, составить таблицу поведения и нарисовать граф автомата Мили, моделирующего блок-схему:
5) Выполнить разметку, составить таблицу поведения и нарисовать граф автомата Мура, моделирующего блок-схему, приведенную в пункте 3).
| <== предыдущая страница | | | следующая страница ==> |
| Автомат Мили - модель управляющего автомата | | | Микропрограммный автомат |
Дата добавления: 2015-07-26; просмотров: 890; Нарушение авторских прав
Мы поможем в написании ваших работ!