3.7. Абстрактна і структурна теорії скінченних автоматів

Під автоматом розуміється пристрій, що самостійно виконує всі операції. Формальний опис автомата називають його логічною структурою. Властивості і методи перетворення логічних структур вивчає теорія кінцевих автоматів, яка підрозділяється на абстрактну і структурну. Абстрактна теорія не торкається структури самого автомата, обмежуючись лише розглядом переходів, що виконуються автоматом при зміні вхідних сигналів, які видаються автоматом у кожному стані. Структурна теорія вивчає способи побудови автоматів, їхню структуру, способи кодування вхідних і вихідних сигналів.

Автомат називається комбінаційним, якщо для будь-якого вхідного символу а і будь-яких станів q_i і q_j (q_i, a)= (q_j, a), інакше кажучи, якщо вихідний символ не залежить від стану і повністю визначається поточним вхідним символом. У такому автоматі всі стани еквівалентні, і, отже, мінімальний комбінаційний автомат має один стан. Функція переходів у ньому вироджена, і його поведінка однозначно задається функцією виходів з одним із аргументів: (a_i)=v_i.

Усі автомати можна розділити на синхронні й асинхронні. Відомі дві моделі синхронних елементарних автоматів: модель Мура і модель Милі, що одержали назви за іменами вчених, які розробили відповідні розділи теорії автоматів. Моделлю Мура називається автомат, що описується рівняннями

q(t) = [x(t-1); q(t-1)]; v(t)=  [q(t)],

де q(t), q(t-1) - стани автомата в моменти часу t і t-1; x(t-1), v(t) - вхідний і вихідний сигнали автомата в моменти часу t і t-1.

Для моделі Милі справедливі співвідношення

q(t) = [x(t-1); q(t-1)];

v(t)=  [x(t); q(t)].

Існує декілька способів представлення скінченних автоматів, основними з яких є графічний, таблично-матричний, аналітичний із використанням секвенціальних рівнянь. Нехай необхідно синтезувати автомат, що дозволяє роботу деякого пристрою при наявності одиничних сигналів на входах Х₁, Х₂ , причому для вмикання пристрою необхідно виконати умову появи сигналу на вході Х₁ раніш ніж на вході Х₂. При графічному способі опису даний автомат можна представити у вигляді спрямованого графа (рис. 3.8 і 3.9), вершинами якого є стан автомата, а ребрами - комбінації вихідних сигналів.

Як очевидно з графа, комбінація (01) викликає перехід автомата з деякого стана S0 у стан S1, що відповідає появі одиничного сигналу на виході У, автомат може перейти тільки зі стана S1 за умови надходження комбінації вхідних сигналів Х₁, Х₂ (11). Даний граф відповідає представленню автомата моделлю Мура, тому що вихідний сигнал (зазначений у вузлах графа) цілком визначається внутрішнім станом автомата і не залежить від комбінації сигналів на вході. При завдаванні автомата моделлю Милі його вихідний сигнал указується над кожним ребром графа ( рис. 3.9), оскількі залежить не тільки від внутрішнього стану автомата, але і від комбінації сигналів, що надходять на вхід автомата в даний момент часу.

00 v 01 v 10

11

11

00 v 01

11

10

01 v 00

10

Рис. 3.8. Граф автомата Мура

10/0

Рис. 3.9. Граф автомата Милі

Замість побудови графа всю необхідну інформацію про роботу можна зводити в спеціальні автоматні таблиці: таблицю переходів і таблицю виходів. Представлення автомата за допомогою таблиць показано в табл. 3.6. - 3.9.

Таблиця 3.6.

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

Стани	Вхідні сигнали
	00	01	11	10
g0	g0	g0	g1	G0
g1	g0	g0	g1	G2
g2	g0	g0	g1	G2

Таблиця 3.7.

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

Стани	g0	g1	g2
Вихідні сигнали	0	0	1

Таблиця 3.8

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

Стани	Вхідні сигнали
	00	01	11	10
g0	G0	g0	G1	g0
g1	g0	g0	G1	g1

Таблиця 3.9

Таблиця виходів автомата Милі

Стани	Выхідні сигнали
	00	01	11	10
g0	0	0	0	0
g1	0	0	0	1

На перетинанні рядків і стовпчиків автоматних таблиць указуються внутрішні стани, в які переходить автомат під дією вхідних сигналів і вихідні сигнали, що він при цьому видає. Обидві розглянутих форми задавання автоматів побудовані для того самого приклада автоматів Мура і Милі.