29. Автомат Мили

Два типа автоматов получили наибольшее распространение на практике: автомат Мили и Мура, названные так по имени впервые исследовавших эти модели американских ученых G.H. Mealy и E.F. Moore.

Автомат Мили

Функционирование автомата Мили задается уравнениями

a(t+1)= [a(t), x(t)];

y(t)=₁[a(t), x(t)];

t=0,1,2,…

Рассмотрим в качестве примера упрощенный вариант автомата, продающего в метро жетоны (рис.4.2).

Рисунок 4.2 – Абстрактный автомат Мили по продаже жетонов

Будем считать, что можно класть в автомат только одну купюру за один сеанс выдачи жетонов. И что можно использовать купюры достоинством 2, 5 и 10 гривен. Также есть кнопка «пуск», которая запускает процесс выдачи жетонов, ее должен нажимать покупатель после захвата купюры автоматом.

Т.е. картина работы автомата выглядит следующим образом. Автомат находится в состоянии ожидания, он готов принимать купюры. Покупатель кладет в автомат определенную ограничениями купюру. Нажимает кнопку «пуск» для подтверждения готовности получения жетонов. Затем автомат выдает жетоны и сдачу, после этого автомат переходит в первоначальное состояние ожидания.

В качестве входных воздействий будем использовать:

x₁ – 2 грн., которые покупатель кладет в автомат;

x₂ – 5 грн., которые покупатель кладет в автомат;

x₃ – 10 грн., которые покупатель кладет в автомат;

x₄ – нажатая кнопка «пуск».

В качестве выходных воздействий будем использовать:

y₁ – выдача 1 жетона и 50 копеек;

y₂ – выдача 3 жетонов и 50 копеек;

y₃ – выдача 6 жетонов и 50+50 копеек;

В качестве внутренних состояний автомата будем использовать:

а₁ – состояние ожидания, когда автомат готов принимать купюры;

а₂ – автомат захватил купюру в 2 грн. и ждет нажатия кнопки «пуск»;

а₃ – автомат захватил купюру в 5 грн. и ждет нажатия кнопки «пуск»;

а₄ – автомат захватил купюру в 10 грн. и ждет нажатия кнопки «пуск»;

a₅ – (выдача жетонов) выдача 1 жетона и 50 копеек;

a₆ – (выдача жетонов) выдача 3 жетонов и 50 копеек;

a₇ – (выдача жетонов) выдача 6 жетонов и 50+50 копеек;

На рис. 4.3 представлен граф переходов автомат Мили по продаже жетонов. Вершинам графа соответствуют состояния автомата, а дугам – переходы между состояниями. Входные воздействия определяют условия переходов из состояния в состояние. Входные воздействия указываются над соответствующими дугами перед наклонной. Если входные состояния не указаны, то переход выполняется безусловно. После наклонной указываются выходные сигналы, которые формируются на переходе из состояния в состояние, т.е. выходные сигналы зависят от условия переходов (входных воздействий) и от состояния, в котором находится автомат.

Рисунок 4.3 – Граф переходов абстрактного автомата Мили по продаже жетонов

Автомат переходит из состояния в состояние под действием входных сигналов, т.е. переход в новое состояние зависти от условия перехода. Выходной сигнал будет формироваться во время перехода из состояния в момент времени t в состояние в момент времени t+1. Например, при переходе автомата из состояния a₅ в состояние a₁, будет формироваться выходной сигнал у₁.