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).

00 v 01 v 10

11

11

00 v 01

11

10

01 v 00

10

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

10/0

Рис. 3.9 - Автомат Милі.

Даний граф відповідає представленню автомата моделлю Мура тому що вихідний сигнал (зазначений у вузлах графа) цілком визначається внутрішнім станом автомата і не залежить від комбінації сигналів на вході. При завданні автомата моделлю Милі його вихідний сигнал указується над кожним ребром графа (див. рис. 3.4), тому що залежить не тільки від внутрішнього стана автомата, але і від комбінації сигналів, що надходять на вхід автомата в даний момент часу.

Замість побудови графа всю необхідну інформацію про роботу можна зводити в спеціальні автоматні таблиці: таблицю переходів і таблицю виходів. Представлення автомата за допомогою таблиць показано в таблицях 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

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