Синтез конечных автоматов

Цель работы: изучение процедура структурного синтеза ко­нечных автоматов.

I. Конечные автоматы

Автоматом называется дискретное устройство, способное при­нимать различные состояния, под воздействием входных сигна­лов переходить из одного состояния в другое и вырабатывать выходные сигналы. Математической моделью устройства является абстрактный автомат, который задается совокупностью пяти объ­ектов S(А,Х, У, d, l) , где

А ={a₀,a₁,a₂, …, a_m, …,a_M} - множество состояний автома­та, причем, a₀- исходное (начальное) состояние;

X = {x₁, x₂,…, x_f,…,x_F } - множество входных сигналов;

У = { y₁, y₂,…, y_g,…,y_G } - множество выходных сигналов;

d - функция переходов, обеспечивающая выработку после­дующего состояния a_S автомата в зависимости от существующего состояния а_т и входного сигнала х_f, т.е.а_S=d(a_m, x_f);

l - функция выходов, обеспечивающая выработку выходного сигнала автомата в зависимости от a_m, и x_f, т.е. y_g=l( a_m, x_f).

Если множества А,Х,У конечны, то автомат называется конечным.

риc.I

Абстрактный автомат имеет один входной и один выходной каналы (рис.1) и функционирует в дискретные моменты времени, которые обычно обозначаются натуральными числами: t= 0, 1, 2,…,n,... . В каждый момент дискретного времени t автомат находится в определенном состоянии a(t), причем в момент t = 0 он всегда находятся в исходном состоянии а(0) =a₀ . В момент t автомат, находясь в состоянии а(t) .восприни­мает сигнал x(t) на входном канале, вырабатывает на выходе сигнал y(t)=l[а(t), x(t)] и переходит в новое состояние, которое к следующему моменту дискретного времени определяет­ся как a(t+1) =d[a(t), х(t)].

Наибольшее распространение получили автоматы Мили и Мура. Закон функционирования автомата Мили задается следующими урав­нениями:

a(t+1) =d[a(t), х(t)]; y(t)=l[a(t), х(t)]. Работа автомата Мура определяется уравнениями:

a(t+1) =d[a(t), х(t)]; y(t)=l[a(t)] . Как видно, в автомате Мура выходные сигналы зависят лишь от состояния автомата.