WikiDer > Машина Мура - Википедия

в теория вычислений, а Машина Мура это конечный автомат чьи выходные значения определяются только его текущим государственный. Это в отличие от Мучная машина, чьи (Мили) выходные значения определяются как его текущим состоянием, так и значениями его входов. Машина Мура названа в честь Эдвард Ф. Мур, который представил концепцию в статье 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. Таблица состояний для этого примера выглядит следующим образом:

Сложный

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Конвей, Дж. (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