Матричный способ задания автоматов

Матричный способ является наиболее общим способом описания автомата. Матрица соединения автомата – квадратная матрица С_ij=||c_ij||, строки которой соответствуют исходным состояниям системы, а столбцы - состояниям переходов. Элемент матрицы c_ij=x_k/y_s, где x_k – входной сигнал, вызывающий переход z_i - > z_j, y_s – значение выходного сигнала, выдаваемое на этом переходе. Для автомата Мура элемент c_ij равен множеству входных сигналов при переходе z_i - > z_j, а выход описывается вектором, i -я компонента которого – это выходной сигнал. C=||C_ij||, строки – исходные состояния, столбцы – состояния перехода.

Элемент C_ij=x_k/y_s, стоящий на пересечении i -й строки и j -го столбца (автомат Мили) – входной сигнал x_k, вызывающий переход из состояния z_i ® z_j и выходной сигнал y_s.

Для автомата Мили матрица соединений:

                                                                            (8)

Если z_i ® z_j происходит под действием нескольких воздействий, то элемент матрицы C_ij – множество пар "вход – выход" для этого перехода, соединенных знаком дизъюнкции.

Для F –аппарата Мура C_ij – множество входных воздействий при переходе (z_i, z_j), а выход описывается вектором выходов

где i -я компонента – выходной сигнал, отмечающий состояние zi.

                                                     ,                                               (9)

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

Рассмотрим таблицу переходов и граф асинхронного конечного автомата. Для F -автомата состояние z_R – устойчивое, если для любого входа x_i Î X, для которого j (z_R, x_i)=z_R, имеет место Y (z_R, x_i)=y_R. Т.о., F -автомат называется асинхронным, если каждое его состояние z_R Î Z устойчиво.

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

1. Автомат Мили:

– табличный способ задания:

xi	zk
	z0	z1	z2
Переходы
x1	z2	z0	z0
x2	z0	z2	z1
выходы
x1	y1	y1	y2
x2	y1	y2	y1

– графовый способ задания:

 

 

– матричный способ задания:

		z0	z1	z2
	z0	x2/y1	–	x1/y1
C1 =	z1	x1/y1	–	x2/y2
	z2	x1/y2	x2/y1

2. Автомат Мура:

– табличный способ задания:

	y
xi	y1	y1	y3	y2	y3
	z0	z1	z2	z3	z4
x1	z1	z4	z4	z2	z2
x2	z3	z1	z1	z0	z0

– матричный способ задания:

 

		z0	z1	z2	z3	z4
	z0	–	x1	–	x2	–			y0
	z1	–	x2	–	–	x1			y1
C =	z2	–	x2	–	–	x1		y =	y2
	z3	x2	–	x1	–	–			y3
	z4	x2	–	x1	–	–			y4

– графовый способ задания: