66.Конечные автоматы. Автоматы Мили и Мура. Канонические уравнения

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

Конечным автоматом называют пятерку объектов S=<A,Q,B,G,ƛ> (1). A={a₁,a₂,…..,a_n} – входной алфавит.B={b₁,b₂,…..,b_m}- выходной алфавит. Q={ q₁,q₂,…..,q_m }-множество внутренних состояний. G:AxQ-> - функция переходов. ƛ:AxQ->B

Таблица, задающая функции переходов называется таблицей состояний автомата. Диаграммой состояний называется ориентированный граф в котором количество вершин равно количеству состояний данного автомата и конечно символами внутренних состояний. Дуга, выходящая из любой вершины q_i, обозначается a_t , b_r при этом б(a_i , b_r)=q_j , ƛ(a_t , q_i ) = b_r Автомат называется инициальным, если он всегда начинает свою работу из одного и того же состояния и неинициальным, если он начинает свою работу с любого состояния. Автомат S в общем случае является частичным и недетермированным

Если B<=A x Q задает отображение Г, то он называется всюду определенным и недетермированным, если задает функциональное отображение Г₃ , то всюду определим детермированным. Поскольку автомат (1) задает функции (2) он относится к всюду определенным детермированным конечным автоматам. Если алфавиты A=B={0,1}, то автомат S называется логическим автоматом. Автомат (1) наз. Конечным автоматом или автоматом 1- го рода, при этом поведения автомата (1) определяются парой функций. q_i(t)=б(q_i(t-1),a_j(t)) b_i(t)= ƛ(q_i(t-1),a_j(t)) q(t-1),q(t) – предыдущие и последующие состояния автомата.

Автомат Мили является синхронным конечным автоматом. {q(t)=б(q(t-1),a(t)) t=1,2,3,… {b(t)= ƛ(q(t-1),a(t)). Для каждого автомата 2 – го рода существует эквивалентный ему автомат 1 – го рода. Между автоматами 1-го и 2-го рода существует взаимооднозначное соответствие (изоморфизм).

Примером автомата 2 – го рода может быть автомат Мура. Его работа описывается функциями вида { q(t)=б(q(t-1),a(t)) {b(t)= ƛ(q(t-1),a(t)). Т.е. выходная буква b есть функция только одного аргумента состояния q(t),не зависит от первой буквы, другими словами автомат Мура автономный автомат(без выходов или генератор)

Работа автоматов Мили связана с двумя бесконечными лентами, разбитыми на ячейки, причем в каждой ячейке может быть записан только один символ некоторого алфавита. Работа над словом α, записанным на входной ленте происходит следующим образом: 1)считав символом

1

1

0

0

1

1

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

2)Работа автомата продолжается до тех пор, пока все ячейки, содержащие слова, не будут пройдены. A={0,1} причин на вход передается бесконечная последовательность символов данного алфавита, а символ 1 печатается только в том случае, когда в данный момент времени считывающее устройство обозревает последний символ прочитанного слова α , при этом слово α называется кодовой комбинацией данного автомата.

Пеннициальный автомат называется сильносвязным или для любых состояний автомата q_i и q_j найдется такое слово α , что автомат , начавший работу в состоянии q_i при считывании слово α передает в состояние q_i.

Автоматы A₁ и A₂ называются эквивалентными, или для любого состояния q_i автомата A₁ найдется эквивалентное ему состояние q_j автомата A₂.;а также для любого состояния q^*_j автомата A₂ найдется эквивалентное ему состояние q^*_I автомата A₁.

Автомат задают следующей системой канонических уравнений: q_i(t+1)=f_i(q₁(t),q₂(t),…,q_n(t)); q_i(1)=q_o , i=1,n; a₁(t),….,a_m(t) b_j(t)=q_j(q₁(t),q_n(t),a₁(t),a_n(t)) j=1,k.