Автоматы Мили и Мура — это конечные автоматы, у которых выходные сигналы являются функциями входного сигнала и/или текущего состояния.
Введение
Электронные цифровые схемы с формальных позиций делятся на следующие классы:
- Комбинационные схемы, то есть схемы, не обладающие памятью. Выходной сигнал обладает зависимостью от совокупности входных данных в текущий момент времени (при учёте задержки на преобразования сигналов). Примерами комбинационных схем могут служить управляемая цифровая шина, мультиплексор и демультиплексор, дешифратор и шифратор, преобразователь кодов, комбинационный счетчик и сумматор и так далее.
- Схемы, обладающие памятью, то есть алгоритм их функционирования обладает зависимостью от состояния входов и памяти о том, что было в предыдущие временные моменты. Данные схемы могут быть описаны с использованием теории конечных автоматов.
Иначе говоря, комбинационными схемами являются логические устройства, которые обрабатывают входной сигнал. А схемы, которые обладают памятью, реагируют на входные сигналы, но в зависимости от заложенных в них данных.
Автоматы Мили и Мура
Абстрактные автоматы призваны реализовать определённые функции, задаваемые разработчиками. Они могут выполнять функции обычного сумматора, могут реализовать какую-нибудь микрокоманду процессора, отбирать нужные данные из оперативной памяти или осуществлять синтаксический анализ выражений.
В общем виде, без учёта различных подробностей, абстрактный автомат может быть представлен следующим образом:
Рисунок 1. Абстрактный автомат. Автор24 — интернет-биржа студенческих работ
Эта иллюстрация схемы абстрактного автомата может быть в математических категориях представлена так:
Рисунок 2. Формула. Автор24 — интернет-биржа студенческих работ
Здесь использованы следующие обозначения:
- Множество {A} является множеством значений на физических входах автомата. На входе в данном случае должна быть определённая очерёдность высоких и низких уровней напряжения, которые предназначены для кодирования логических нулей и единиц.
- Множество {B} является множеством значений на физических выходах автомата.
- Множество {C} является множеством, представляющем внутреннее состояние автомата, то есть, память. Следует отметить, что C0 обозначает исходное состояние автомата.
- δ = X × Z → Z являются функциями переходов автомата, они способны однозначно определить состояние ai в которое должен перейти автомат из состояния aj.
- λ = X × Z → Y являются функциями выходов, они должны определять то, что будет на выходе автомата в зависимости от сигналов на входах и внутреннего состояния.
Функции δ и λ не изображены на рисунке один с целью визуального упрощения. Подобный автомат должен работать дискретно по времени, то есть значения входов, выходов и внутреннее состояние автомата должны изменяться в определённые дискретные моменты времени. Примерами, описанных выше абстрактных автоматов, могут служить триггеры, регистры компьютеров или сумматоры.
Существует два основных типа абстрактных автоматов:
- Автоматы Мили.
- Автоматы Мура.
Автоматы Мили могут быть описаны следующей системой уравнений:
$c(t) = δ( a(t), c(t-1) )$;
$b(t) = λ( a(t), c(t-1) )$.
А автоматы Мура описываются такой системой уравнений:
$c(t) = δ( a(t), c(t-1) )$;
$b(t) = λ( a(t), c(t) )$.
Как следует из приведённых формул, состояние автомата c(t) в текущий момент времени выступает как функция его состояния в предыдущий момент времени и входного сигнала. Отличие этих двух автоматов заключается в виде функции выхода. В автомате Мили выходной сигнал должен определяться входным сигналом a(t) и состоянием автомата в предыдущий момент времени c(t-1). Выходной сигнал автомата Мура должен определяться входным сигналом a(t) и состоянием в данный момент c(t).
Кроме того, следует заметить, что возможен переход от первого типа ко второму и наоборот. При этом, при переходе от автомата Мили к автомату Мура количество внутренних состояний автомата остаётся прежним, а при обратном переходе количество внутренних состояний способно увеличиться.
То есть, автомат типа Мили формирует выходной сигнал тогда, когда у него изменяется входной сигнал, в зависимости от его предыдущего состояния. Причём длительность выходного сигнала не имеет зависимости от длительности входного сигнала, а зависит только от его наличия.
В автоматах типа Мура выходной сигнал имеет зависимость от состояния автомата в текущий момент времени, то есть, автомат станет формировать определенный выходной сигнал до тех пор, пока он не изменит своё состояние.
Далее следует рассмотреть методы задания автоматов. Как отмечалось выше, абстрактный автомат является совокупностью входного и выходного алфавитов, множества внутренних состояний и функций, которые определяют переходы и выходы. Тем не менее функции δ и λ, как правило, не являются заданными, и поведение автомата должно быть описано иначе. Известны следующие основные способы задания абстрактных автоматов:
- С помощью графов.
- С помощью таблиц переходов и выходов.
Графом автомата является ориентированный связный граф, вершины которого представляют собой внутренние состояния автомата, а дуги считаются переходами из одного состояния в другое. На рисунке три показан граф автомата Мили.
Рисунок 3. Граф автомата Мили. Автор24 — интернет-биржа студенческих работ
Для графа Мили на дугах должны быть указаны входные и выходные буквы. Выходные буквы должны быть написаны над дугами, что должно символизировать тот факт, что выходное состояние обладает зависимостью от состояния автомата в предыдущий момент времени.
Для графа автомата Мура на дугах должны быть записаны только входные буквы, выходные же должны быть указаны около вершин, как показано на рисунке четыре.
Рисунок 4. Граф автомата Мура. Автор24 — интернет-биржа студенческих работ
Необходимо отметить одно важное обстоятельство - если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат считается полным. Говоря иначе, если из каждой вершины определяются переходы для каждой входной буквы, то автомат является полным. В приведённых примерах автомат Мили может считаться полным, а автомат Мура является лишь частичным.
