Машина Мура - Moore machine

в теория вычислений, а Машина Мура это конечный автомат чьи выходные значения определяются только его текущим государственный. Это в отличие от Мучная машина, чьи (Мили) выходные значения определяются как его текущим состоянием, так и значениями его входов. Машина Мура названа в честь Эдвард Ф. Мур, который представил концепцию в статье 1956 года, «Геданкен-эксперименты на последовательных машинах ».^[1]

Формальное определение

Машину Мура можно определить как 6-кратный ${\displaystyle (Q,q_{0},\Sigma ,O,\delta ,G)}$ состоящий из следующего:

• Конечный набор состояния ${\displaystyle Q}$
• Начальное состояние (также называемое начальным состоянием) ${\displaystyle q_{0}}$ который является элементом ${\displaystyle Q}$
• Конечное множество, называемое входом алфавит ${\displaystyle \Sigma }$
• Конечное множество, называемое выходом алфавит ${\displaystyle O}$
• Переход функция ${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$ отображение состояния и входного алфавита на следующее состояние
• Функция вывода ${\displaystyle G:Q\rightarrow O}$ отображение каждого состояния в выходной алфавит

Машину Мура можно рассматривать как ограниченный тип конечный преобразователь.

Визуальное представление

Стол

Таблица перехода состояний - таблица, показывающая связь между вводом и состоянием.^{[требуется разъяснение ]}

Диаграмма

В диаграмма состояний для машины Мура или диаграммы Мура - это диаграмма, которая связывает выходное значение с каждым состоянием. Машина Мура является производителем выходных данных.

Связь с машинами Мили

Поскольку машины Мура и Мили являются типами конечных автоматов, они одинаково выразительны: любой тип может использоваться для анализа обычный язык.

Разница между машинами Мура и Мучные машины состоит в том, что в последнем случае выход перехода определяется комбинацией текущих государственный и текущий ввод (${\displaystyle S\times \Sigma }$ как вход в ${\displaystyle G}$), а не только текущее состояние (${\displaystyle S}$ как вход в ${\displaystyle G}$). Когда он представлен как диаграмма состояний,

• для машины Мура каждый узел (состояние) помечен выходным значением;
• для машины Мили каждая дуга (переход) помечена выходным значением.

Каждая машина Мура ${\displaystyle M}$ эквивалентна машине Мили с теми же состояниями и переходами, а функция вывода ${\displaystyle G(s,\sigma )\rightarrow G_{M}(\delta _{M}(s,\sigma ))}$, который принимает каждую пару состояние-вход ${\displaystyle (s,\sigma )}$ и дает ${\displaystyle G_{M}(\delta _{M}(s,\sigma ))}$, куда ${\displaystyle G_{M}}$ является ${\displaystyle M}$функция вывода и ${\displaystyle \delta _{M}}$ является ${\displaystyle M}$функция перехода.

Однако не каждую машину Мили можно преобразовать в эквивалентную машину Мура. Некоторые могут быть преобразованы только в почти эквивалентная машина Мура, со смещенными во времени выходами. Это связано с тем, что метки состояния соединяются с метками перехода для формирования пар ввода / вывода. Рассмотрим переход ${\displaystyle s_{i}\rightarrow s_{j}}$ от государства ${\displaystyle s_{i}}$ заявить ${\displaystyle s_{j}}$. Вход, вызывающий переход ${\displaystyle s_{i}\rightarrow s_{j}}$ маркирует край ${\displaystyle (s_{i},s_{j})}$. Выход, соответствующий этому входу, является меткой состояния ${\displaystyle s_{i}}$.^[2] Обратите внимание, что это исходное состояние перехода. Таким образом, для каждого входа выход уже фиксирован до того, как вход получен, и зависит исключительно от текущего состояния. Это первоначальное определение Э. Мура. Использование ярлыка состояния - распространенная ошибка. ${\displaystyle s_{j}}$ как выход для перехода ${\displaystyle s_{i}\rightarrow s_{j}}$.

Примеры

Типы по количеству входов / выходов.

Простой

Простые машины Мура имеют один вход и один выход:

• детектор края с помощью XOR
• двоичная суммирующая машина
• синхронизированные последовательные системы (ограниченная форма машины Мура, где состояние изменяется только при изменении глобального тактового сигнала)

Большинство цифровых электронных систем разработаны как синхронизированные последовательные системы. Тактовые последовательные системы - это ограниченная форма машины Мура, где состояние изменяется только при изменении глобального тактового сигнала. Обычно текущее состояние хранится в шлепки, а глобальный тактовый сигнал подключается ко входу «тактового сигнала» триггеров. Тактовые последовательные системы - один из способов решения метастабильность проблемы. Типичная электронная машина Мура включает комбинационная логика цепочка для декодирования текущего состояния в выходы (лямбда). В тот момент, когда изменяется текущее состояние, эти изменения проходят через эту цепочку, и почти мгновенно вывод обновляется. Существуют методы проектирования, гарантирующие, что глюки происходят на выходах в течение этого короткого периода, пока эти изменения распространяются по цепочке, но большинство систем спроектировано так, что сбои в течение этого короткого времени перехода игнорируются или не имеют значения. Затем выходы остаются неизменными бесконечно (Светодиоды оставаться ярким, питание остается подключенным к двигателям, соленоиды оставаться под напряжением и т. д.), пока машина Мура снова не изменит состояние.

Пример работы

Последовательная сеть имеет один вход и один выход. Выход становится 1 и остается 1 после этого, когда по крайней мере два нуля и две единицы встречаются в качестве входных данных.

Пример мур-машины

Справа показана машина с девятью состояниями для приведенного выше описания. Начальное состояние - состояние A, а конечное состояние - состояние I. Таблица состояний для этого примера выглядит следующим образом:

Текущее состояние	Вход	Следующее состояние	Выход
А	0	D	0
	1	B
B	0	E	0
	1	C
C	0	F	0
	1	C
D	0	грамм	0
	1	E
E	0	ЧАС	0
	1	F
F	0	я	0
	1	F
грамм	0	грамм	0
	1	ЧАС
ЧАС	0	ЧАС	0
	1	я
я	0	я	1
	1	я

Сложный

Более сложные машины Мура могут иметь несколько входов, а также несколько выходов.

Геданкен-эксперименты

В статье Мура "Геданкен-эксперименты на последовательных машинах »,^[1] то ${\displaystyle (n;m;p)}$ автоматы (или машины) ${\displaystyle S}$ определяются как имеющие ${\displaystyle n}$ состояния, ${\displaystyle m}$ входные символы и ${\displaystyle p}$ выходные символы. Доказаны девять теорем о строении ${\displaystyle S}$, и эксперименты с ${\displaystyle S}$. Потом, "${\displaystyle S}$ машины »стали называть« машинами Мура ».

В конце статьи, в разделе «Дальнейшие проблемы», ставится следующая задача:

Другая непосредственно следующая проблема - это улучшение оценок, приведенных в теоремах 8 и 9.

Теорема Мура 8 сформулирована следующим образом:

Учитывая произвольную ${\displaystyle (n;m;p)}$ машина ${\displaystyle S}$, такое, что каждые два его состояния отличимы друг от друга, то существует эксперимент длины ${\displaystyle {\tfrac {n(n-1)}{2}}}$ что определяет состояние ${\displaystyle S}$ в конце эксперимента.

В 1957 г. А. А. Карацуба доказал следующие две теоремы, полностью решившие проблему Мура об улучшении оценок длины эксперимента его «Теоремы 8».

Теорема А. Если ${\displaystyle S}$ является ${\displaystyle (n;m;p)}$ машина такая, что каждые два ее состояния отличимы друг от друга, то существует разветвленный эксперимент продолжительностью не более ${\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1}$ по которому можно определить состояние ${\displaystyle S}$ в конце эксперимента.

Теорема Б. Существует ${\displaystyle (n;m;p)}$ машины, каждые два состояния которой различимы друг от друга, так что продолжительность кратчайших экспериментов, устанавливающих состояние машины в конце эксперимента, равна ${\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1}$.

Теоремы А и Б легли в основу курсовой работы студента четвертого курса Карацубы А.А. «К задаче из теории автоматов», которая была отмечена отзывом на конкурсе студенческих работ факультета механики и математики МГУ им. М.В. Ломоносова в 1958 г. Статья Карацубы передана в журнал. Успехи матем. Наук 17 декабря 1958 г. и был опубликован там в июне 1960 г.^[3]

До настоящего времени (2011 г.) результат Карацубы о продолжительности экспериментов является единственным точным нелинейным результатом как в теории автоматов, так и в аналогичных задачах теории сложности вычислений.

Смотрите также

• Синхронная схема
• Мучная машина
• Алгоритмический конечный автомат
• Автономная система (математика)

Рекомендации

1. Мур, Эдвард Ф (1956). «Геданкен-эксперименты на последовательных машинах». Исследования автоматов, Анналы математических исследований. Принстон, Нью-Джерси: Издательство Принстонского университета (34): 129–153.
2. Ли, Эдвард Эшфорд; Сешия, Санджит Арункумар (2013). Введение во встраиваемые системы (1.08 ред.). Калифорнийский университет в Беркли: Lulu.com. ISBN  9780557708574. Получено 1 июля 2014.
3. Карацуба, А.А. (1960). «Решение одной задачи из теории конечных автоматов». Успехи матем. Наук (15:3): 157–159.

дальнейшее чтение

• Конвей, Дж. (1971). Регулярная алгебра и конечные машины. Лондон: Чепмен и Холл. ISBN  0-412-10620-5. Zbl  0231.94041.
• Мур Э. Ф. Геданкен-эксперименты на последовательных машинах. Исследования автоматов, Анналы математических исследований, 34, 129–153. Издательство Принстонского университета, Принстон, Нью-Джерси (1956).
• Карацуба А. А. Решение одной задачи теории конечных автоматов. Усп. Мат. 1960. Т. 15: 3. С. 157–159.
• Карацуба А. А. Experimente mit Automaten (нем.) Elektron. Информация Кибернетик, 11, 611–612 (1975).
• Карацуба А.А. Список исследовательских работ.

Машина Мура и Мили

внешняя ссылка

• СМИ, связанные с Машина Мура в Wikimedia Commons