Автоматы Мили и Мура

На практике наибольшее распространение получили два типа конечных автоматов: автомат Мили и автомат Мура. Поведение автомата Мили описывается с помощью следующих

a_t+1 = (z_t, a_t); (1)

w_t = (z_t, a_t); где t = 0, 1, 2,...

здесь функция переходов a_t+1 определяет следующее внутреннее состояние автомата (состояние перехода, а функция выходов w_t - формируемый выходной набор. Характерным для автомата Мили является то, что выходной набор w_t зависит как от входного набора z_t, так и от внутреннего состояния a_t.

В автомате Мура функция выходов зависит только от состояния at и не зависит от входного набора, поэтому поведение автомата Мура описывается следующими уравнениями:

a_t+1 = (z_t, a_t); (2)

w_t = (a_t); где t = 0, 1, 2....

При построении конечных автоматов функции переходов и выходов реализуются с помощью комбинационных схем CL_Φ и CL_Ψ, соответственно, а память автомата реализуется в виде регистра RG, где в каждый момент автоматного времени t~ хранится код внутреннего состояния a_t. Структурные схемы автоматов Мили и Мура показаны на рис. 1а и 1б, соответственно. Особенностью структуры автомата Мура является то, что комбинационная схема CL_Ψ, реализующая выходные функции, не имеет непосредственной связи со входами схемы.

Рис. 2. Основные структуры конечных автоматов:

а - Мили класса A; б - Мура класса B;

в - Мура класса С; г - Мили класса D;

д - Мили класса E; е - Мура класса F;