1. Визначення автоматів та їх класифікація. Автомати Мілі і Мура.

Автоматом називається п’ятірка (A,X,Z,F,).

А – множина станів {a₀, a₁,……,a_n}.

X – вхідний алфавіт {x₀, x₁,……,x_m}.

Z – вихідний алфавіт {z₀,z₁,…..,z_k}.

F – функція переходів яка визначає в якому стані буде перебувати автомат за певного набору вхідних сигналів та його стану в попередній момент часу.

F = f(a₀, a₁,……,a_n,aj, x₀, x₁,……,x_m)

 - множина функцій виходу.

Функція виходів визначає яких значень буде набувати сигнал на виході автомата. Ця функція може на залежати явним чином від вхідних сигналів, а визначається тільки станом автомату в даний момент часу.

Класифікація автоматів:

1. По обсягу пам’яті.

• Скінченні (пам'ять визначається кількістю комірок) - скінченна кількість внутрішніх станів.

• Нескінченні – нескінченна кількість внутрішніх станів.

2. Механізм вбору.

• Детерміновані – автомати в яких функція переходів є однозначною, або чітко визначеною.

• Недетерміновані – автомат який може переходити за певних умов в декілька станів, але імовірність переходу є невизначеною.

• Імовірнісні – при певному наборі вхідних сигналів та певному внутрішньому стані може перейти не в один, а в декілька станів, однак імовірність переходу в кожний з цих станів є чітко визначеним.

3. Синхронні та асинхронні.

• Синхронні – в них весь часовий проміжок розбивається на дискретні відрізки , тому переходи здійснюються тільки під впливом сигналів в певний момент часу, а вихідні сигнали визначаються в наступний відлік часу.

• Асинхронні – внутрішні переходи та сигнали на виході здійснюються через деякий час і можуть залежати від вхідних сигналів в будь який момент часу.

Якщо вихідний сигнал в момент часу t однозначно визначається станом автомату в той же момент часу z(t) = (a(t)), то автомат називається автоматом Мура.

Закон функционирования автомата Мура задается уравнениями:

a(t+1)=d(a(t), z(t)); w(t) = l(a(t)), t = 0,1,2,...

Таблиця переходів автомата Мура.

Вхідний сигнал	Вихідний сигнал
	z2	z2	z2	z1	z2	z3
	Стан
	a0	a1	a2	a3	a4	a5
x1	a1	a2	a2	a4	a4	a1
X2	a0	a0	a0	a5	a5	a0

Якщо z(t) = (a(t), x(t)) значення вихідного сигналу залежить не тільки від стану автомата а й від значеть вхідного сигналу, то це автомат Мілі.

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t), z(t)), t = 0,1,2,...

Таблиця переходів автомата Мілі.

Вхідний сигнал	Стан
	a0	a1	a2	a3
	a1 z2	a2 z3	a3 z1	a3 z2
	a0 z2	a0 z2	a0 z2	a0 z3