Рекуррентные формулы задания автомата

- Это Каноническое уравнение автомата

Способы задания конечного автомата:

1) Табличный

x(t)	z(t-1)	y(t)	Z(t)
A	Q	F	G

2) Аналитический (формульный)

3) Графический

	F(a, q) = b G(a, q) = q’

Получим Диаграмму Мура

Определение. Диаграмма Мура это ориентированный корневой граф:

(а) множество вершин которого совпадает с множеством q;

(б) пусть (a, b) a Î A, b Î B такие что для "q Î Q и для "a Î A существует ровно одно ребро, выходящее из вершины q, в котором первая буква – а.

Примеры автоматов:

1) Тривиальный Q = {q₀}, t = 0

y(t) = F(x(t)), y = F(x)

A = B = E₂ = {0; 1}

x(t)	z(t-1)	y(t)	z(t)		Диаграмма Мура:
	q0		q0
	q0		q0

2) Автомат задержек

A = B = Q = {0; 1}

Определение

x(1) = 0 y(1) = z(0) = 0

x(t)	z(t-1)	y(t)	z(t)		Диаграмма Мура:
0		0
0		1

3) Автомат с тремя состояниями (покой, возбуждение и промежуточное положение):

A = B = E₂,

x(t)	z(t-1)	y(t)	z(t)
	q0		q2
	q0		q2
	q0		q0
	q0		q0
	q0		q1
	q0		q1