Машина Мура

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

Формальное определение [ править ]

Машину Мура можно определить как набор из шести элементов, состоящий из следующих элементов:${\ 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}$

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

Каждая машина Мур эквивалентна Миля машины с теми же состояниями и переходами и выходной функцией , которая принимает каждое состояние входной пару и выходы , где это «ы функция выхода и это » s функция перехода.${\ 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}$

Однако не каждую машину Мили можно преобразовать в эквивалентную машину Мура. Некоторые из них могут быть преобразованы только в почти эквивалентную машину Мура со сдвигом по времени. Это связано с тем, что метки состояния объединяются с метками перехода для формирования пар ввода / вывода. Рассмотрим переход из состояния в состояние . Вход, вызывающий переход, помечает край . Выход, соответствующий этому входу, является меткой состояния . ^[2]${\ 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}}$Обратите внимание, что это исходное состояние перехода. Таким образом, для каждого входа выход уже фиксирован до того, как вход получен, и зависит исключительно от текущего состояния. Это первоначальное определение Э. Мура. Распространенная ошибка - использовать метку состояния в качестве вывода для перехода .${\ 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}$

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

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

Внешние ссылки [ править ]

• СМИ, связанные с машиной Мура, на Викискладе?