Автоматы Мура и Мили
Версия от 23:28, 7 января 2015; Alive (обсуждение | вклад) (→Табличный способ задания автомата Мили)
Содержание
Абстрактные автоматы
Определение: |
Абстрактный автомат (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором 1. - множество состояний.2. - множество входных сигналов.3. - множество выходных сигналов.4. - функция переходов АА, которая некоторым парам \<состояние - входной сигнал\> ( , ) ставит в соответствие состояние АА , т.е. , .5. 6. - функция выходов АА, которая некоторым парам \<состояние – входной сигнал\> ( , ) ставит в соответствие выходной сигнал АА , т.е. , . - начальное состояние. АА работает в дискретные моменты времени, и в момент времени автомат всегда находится в состоянии . | , где
Выходные сигналы АА зависят от того, что поступало на его вход раньше.
В каждый момент времени АА, будучи в состоянии
, способен воспринимать одну из букв входного алфавита . В соответствии с функцией , АА перейдет в состояние с выдачей выходного сигнала, который вырабатывается в соответствии с функцией выходов .Рассмотрим функционирование автоматов Мура и Мили.
Автомат Мили
|
Автомат Мура
|
В автоматах Мура выходной сигнал определяется только состоянием автомата в какой-то момент времени и не зависит от входного сигнала в этот же момент времени.
Способы задания автоматов
Табличный способ задания автомата Мили
Автомат Мили может быть задан таблицей переходов и таблицей выходов.
В таблице переходов АА Мили на пересечении столбца
и строки записывается состояние , которое есть функция от иВ таблице выходов на пересечении столбца
и строки записывается выходной сигнал, который есть функция от и .Табличный способ задания автомата Мура
В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала. Поэтому достаточно для задания автомата Мура в таблице переходов добавить одну строку.