В теории вычислений , A Мучнистый машин представляет собой конечный автомат , чьи значения выходного определяются как его текущим состоянием и текущими входами. Это отличается от машины Мура, выходные значения которой (Мура) определяются исключительно ее текущим состоянием. Машина Мили - это детерминированный преобразователь с конечным числом состояний : для каждого состояния и входа возможен не более одного перехода.
История
Машина Мили названа в честь Джорджа Х. Мили , который представил эту концепцию в статье 1955 года «Метод синтеза последовательных цепей». [1]
Формальное определение
Машина Мили - это кортеж из шести состоящий из следующего:
- конечное множество из состояний
- начальное состояние (также называемое начальным состоянием) который является элементом
- конечное множество называется входной алфавит
- конечное множество называется выходной алфавит
- функция перехода отображение пар состояния и входного символа в соответствующее следующее состояние.
- функция вывода отображение пар состояния и входного символа на соответствующий выходной символ.
В некоторых формулировках функции перехода и вывода объединены в одну функцию. .
Сравнение машин Мили и Мура
- Аппараты Мили, как правило, имеют меньше состояний:
- Различные выходы на дугах ( n 2 ), а не на состояниях ( n ).
- Машины Мура безопаснее использовать:
- Выходы изменяются по фронту тактового сигнала (всегда на один цикл позже).
- В машинах Мили изменение входа может вызвать изменение выхода, как только логика выполняется - большая проблема, когда две машины связаны между собой - асинхронная обратная связь может возникнуть, если вы не будете осторожны.
- Аппараты Мили быстрее реагируют на вводимые данные:
- Реагируйте в том же цикле - не нужно ждать часов.
- В машинах Мура может потребоваться больше логики для декодирования состояния в выходы - больше задержек затвора после фронта тактового сигнала.
Диаграмма
Диаграмма состояний для Мили машины связывает выходное значение с каждым переходом краем, в отличии от диаграммы состояний для машины Мура, который связывает выходное значение с каждым состоянием.
Когда входной и выходной алфавит являются Σ , можно также связать с автоматами Мили ориентированный по спирали граф [ требуется пояснение ] ( S × Σ, ( x , i ) → ( T ( x , i ), G ( x , i) ))) . [2] Вершинами этого графа являются пары состояний и букв, все узлы имеют исходную степень один, а преемник ( x , i ) - это следующее состояние автоматов и буква, которую выводит автомат, когда он установить x, и он читает букву i . Этот граф является объединением непересекающихся циклов, если автомат двунаправлен [ требуется определение ] .
Примеры
Простой
Простая машина Мили имеет один вход и один выход. Каждый край перехода помечен значением входа (показано красным) и значением выхода (показано синим). Машина запускается в состоянии S i . (В этом примере выходом является исключающее ИЛИ из двух самых последних входных значений; таким образом, машина реализует детектор края, выводя единицу каждый раз, когда вход переворачивается, и ноль в противном случае.)
Сложный
Более сложные машины Мили могут иметь как несколько входов, так и несколько выходов.
Приложения
Машины Мили представляют собой элементарную математическую модель для шифровальных машин. Рассматривая , например, входной и выходной алфавит, латинский алфавит , тогда машина Мили может быть спроектирована так, чтобы заданная строка букв (последовательность входных данных) могла преобразовать ее в зашифрованную строку (последовательность выходных данных). Однако, хотя модель Мили может быть использована для описания Enigma , диаграмма состояний будет слишком сложной, чтобы предоставить возможные средства проектирования сложных шифровальных машин.
Машины Мура / Мили - это DFA , которые также выводят данные в любой момент времени. Современные процессоры, компьютеры, сотовые телефоны, цифровые часы и базовые электронные устройства / машины имеют какой-то конечный автомат для управления ими.
Простые программные системы, особенно те, которые могут быть представлены с помощью регулярных выражений, можно моделировать как конечные автоматы. Существует множество таких простых систем, как торговые автоматы или базовая электроника.
Обнаружив пересечение двух конечных автоматов, можно очень просто спроектировать параллельные системы, например, обменивающиеся сообщениями. Например, светофор - это система, состоящая из нескольких подсистем, таких как разные светофоры, которые работают одновременно.
Некоторые примеры приложений:
- классификация номеров
- часы с таймером
- торговый автомат
- светофор
- Сканер штрих-кода
- газовые насосы
Смотрите также
Сноски
- ^ Мили, Джордж Х. (сентябрь 1955 г.). «Метод синтеза последовательных цепей». Технический журнал Bell System . 34 : 1045–1079. DOI : 10.1002 / j.1538-7305.1955.tb03788.x .
- ^ Ахави и др. (2012)
Рекомендации
- Мили, Джордж Х. (1955). Метод синтеза последовательных схем . Технический журнал Bell System. С. 1045–1079.
- Холкомб, WML (1982). Теория алгебраических автоматов . Кембриджские исследования в области высшей математики. 1 . Издательство Кембриджского университета . ISBN 0-521-60492-3. Zbl 0489.68046 .
- Рот, Чарльз Х., младший (2004). Основы логического дизайна . Томсон-Инжиниринг. С. 364–367. ISBN 0-534-37804-8.
- Ахави, Али; Климанн, Инес; Ломбардия, Сильвен; Mairesse, Жан; Пикантин, Матье (2012). «О проблеме конечности автоматных (полу) групп». Int. J. Algebra Comput . 22 (6). arXiv : 1105,4725 . Bibcode : 2011arXiv1105.4725A . Zbl 1280.20038 .
Внешние ссылки
- СМИ, связанные с машиной Мили на Викискладе?