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

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

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

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

  • Конечный набор состояний
  • Начальное состояние (также называемое начальным состоянием), которое является элементом
  • Конечное множество, называемое входным алфавитом
  • Конечное множество, называемое выходным алфавитом
  • Переход функции отображения состояния и входного алфавита к следующему состоянию
  • Функция вывода, отображающая каждое состояние в алфавит вывода

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

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

Таблица

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

Диаграмма

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

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

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

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

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

Каждая машина Мур эквивалентна Миля машины с теми же состояниями и переходами и выходной функцией , которая принимает каждое состояние входной пару и выходы , где это «ы функция выхода и это » s функция перехода.

Однако не каждую машину Мили можно преобразовать в эквивалентную машину Мура. Некоторые из них могут быть преобразованы только в почти эквивалентную машину Мура со сдвигом по времени. Это связано с тем, что метки состояния объединяются с метками перехода для формирования пар ввода / вывода. Рассмотрим переход из состояния в состояние . Вход, вызывающий переход, помечает край . Выход, соответствующий этому входу, является меткой состояния . Обратите внимание, что это исходное состояние перехода. Таким образом, для каждого входа выход уже фиксирован до того, как вход получен, и зависит исключительно от текущего состояния. Это первоначальное определение Э. Мура. Распространенная ошибка - использовать метку состояния в качестве вывода для перехода .

Примеры

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

Простой

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

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

альтернативный текст

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

Последовательная сеть имеет один вход и один выход. Выход становится 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 я

Сложный

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

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

В статье Мура « Геданкен-эксперименты на последовательных машинах» автоматы (или машины) определяются как имеющие состояния, входные символы и выходные символы. Доказано девять теорем о структуре и экспериментах с . Позже « машины» стали называть «машинами Мура».

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

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

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

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

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

Теорема А. Если это машина, таким образом, что каждые два из его состояний различимы друг от друга, то существует разветвленный эксперимент длины по большей мере , через которую можно определить состояние в конце эксперимента.

Теорема B. Существует машина, каждые два состояния которой отличимы друг от друга, так что продолжительность кратчайших экспериментов, устанавливающих состояние машины в конце эксперимента, равна .

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

До настоящего времени (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).
  • Карацуба А.А. Список научно-исследовательских работ .

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

Внешние ссылки