Машина для помола муки

Машина, выход которой определяется ее состоянием и входами

В теории вычислений автомат Мили — это конечный автомат , выходные значения которого определяются как его текущим состоянием , так и текущими входами. Это контрастирует с автоматом Мура , выходные значения которого определяются исключительно его текущим состоянием. Автомат Мили — это детерминированный конечный преобразователь : для каждого состояния и входа возможен максимум один переход.

История

Машина Мили названа в честь Джорджа Х. Мили , который представил эту концепцию в статье 1955 года «Метод синтеза последовательных цепей». ^[1]

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

Автомат Мили представляет собой 6-кортеж, состоящий из следующих элементов: ${\displaystyle (S,S_{0},\Sigma ,\Lambda ,T,G)}$

• конечный набор состояний​ ${\displaystyle S}$
• начальное состояние (также называемое начальным состоянием), которое является элементом ${\displaystyle S_{0}}$ ${\displaystyle S}$
• конечный набор, называемый входным алфавитом ${\displaystyle \Sigma }$
• конечный набор, называемый выходным алфавитом ${\displaystyle \Lambda }$
• функция перехода , отображающая пары состояния и входного символа в соответствующее следующее состояние. ${\displaystyle T:S\times \Sigma \rightarrow S}$
• выходная функция, сопоставляющая пары состояния и входного символа с соответствующим выходным символом. ${\displaystyle G:S\times \Sigma \rightarrow \Lambda }$

В некоторых формулировках функции перехода и выхода объединены в одну функцию . ${\displaystyle T:S\times \Sigma \rightarrow S\times \Lambda }$

«Эволюция во времени» реализуется в этой абстракции посредством того, что конечный автомат обращается к изменяющемуся во времени входному символу в дискретные «такты таймера» и реагирует в соответствии со своей внутренней конфигурацией в эти идеализированные моменты, или же посредством того, что конечный автомат ждет следующего входного символа (как в FIFO) и реагирует всякий раз, когда он поступает. ${\displaystyle t_{0},t_{1},t_{2},...}$

Сравнение машин Мили и машин Мура

1. Автоматы Мили, как правило, имеют меньше состояний:
   • Различные выходы на дугах ( n ² ), а не на состояниях ( n ).
2. При реализации в виде электронных схем (а не в виде математических абстракций или кода):
   • Машины Мура безопаснее в использовании, чем машины Мили:
     • Выходные сигналы изменяются по фронту тактового сигнала (всегда на один цикл позже).
     • В автоматах Мили изменение входных данных может вызвать изменение выходных данных сразу после завершения логики — серьезная проблема, если две машины соединены между собой: если одна из них не будет осторожна, может возникнуть асинхронная обратная связь.
   • Машины Мили быстрее реагируют на входные данные:
     • Реагируйте в том же цикле — им не нужно ждать, пока остановятся часы.
     • В машинах Мура может потребоваться больше логики для декодирования состояния в выходы — больше задержек вентилей после фронта тактового импульса.

Диаграмма

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

Когда входной и выходной алфавиты являются Σ , можно также связать с автоматом Мили ориентированный граф Helix ^{[ требуется пояснение ]} ( S × Σ, ( x , i ) → ( T ( x , i ), G ( x , i ))) . ^[2] Этот граф имеет в качестве вершин пары состояний и букв, каждый узел имеет исходящую степень один, а преемник ( x , i ) является следующим состоянием автомата и буквой, которую автомат выводит, когда он находится в состоянии x и читает букву i . Этот граф является объединением непересекающихся циклов, если автомат является двуобратимым ^{[ требуется определение ]} .

Примеры

Простой

Диаграмма состояний для простого автомата Мили с одним входом и одним выходом. (Для каждого входного значения выводится 1, если текущее входное значение отличается от предыдущего, или 0 в противном случае.)

Простая машина Мили имеет один вход и один выход. Каждое ребро перехода помечено значением входа (показано красным) и значением выхода (показано синим). Машина запускается в состоянии S _i . (В этом примере выход представляет собой исключающее ИЛИ двух последних входных значений; таким образом, машина реализует детектор краев, выводя 1 каждый раз, когда вход переключается, и 0 в противном случае.)

Сложный

Более сложные машины Мили могут иметь как несколько входов, так и несколько выходов. ^{[ необходима цитата ]}

Приложения

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

Машины Мура/Мили — это DFA , которые также имеют выход в любой такт часов. Современные процессоры, компьютеры, сотовые телефоны, цифровые часы и базовые электронные устройства/машины имеют своего рода конечный автомат для управления.

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

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

Некоторые примеры приложений:

• классификация чисел
• часы с таймером
• торговый автомат
• светофор
• сканер штрих-кода
• газовые насосы

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

• Синхронная цепь
• машина Мура
• Алгоритмическая машина состояний
• Контролер Ричардса

Сноски

1. Мили, Джордж Х. (сентябрь 1955 г.). «Метод синтеза последовательных цепей». Bell System Technical Journal . 34 (5): 1045–1079. doi :10.1002/j.1538-7305.1955.tb03788.x.
2. Ахави и др. (2012)

Ссылки

• Мили, Джордж Х. (1955). Метод синтеза последовательных цепей . Bell System Technical Journal. С. 1045–1079.
• Холкомб, В. М. Л. (1982). Алгебраическая теория автоматов . Кембриджские исследования по высшей математике. Том 1. Cambridge University Press . ISBN 0-521-60492-3. Збл  0489.68046.
• Рот, Чарльз Х. младший (2004). Основы логического проектирования . Thomson-Engineering. стр. 364–367. ISBN 0-534-37804-8.
• Ахави, Али; Климанн, Инес; Ломбарди, Сильвен; Мэресс, Жан; Пикантен, Матье (2012). «О проблеме конечности для автоматных (полу)групп». Международный журнал алгебры и вычислений . 22 (6). arXiv : 1105.4725 . Bibcode :2011arXiv1105.4725A. doi :10.1142/S021819671250052X. S2CID  47518684. Zbl  1280.20038.

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

• Медиа, связанные с машиной Мили на Wikimedia Commons