Если заменить внутреннюю переменную q на соответствующий булев вектор z (z1, z2, … , zk), то получится система уравнений, в которой все переменные и все функции оказываются булевыми:

z1+ = 1х1, х2, … , хп; z1, z2, … , zk;
z2+ = 2х1, х2, … , хп; z1, z2, … , zk;
…
zk+ = kх1, х2, … , хп; z1, z2, … , zk;
y1 = 1х1, х2, … , хп; z1, z2, … , zk;
y2 = 2х1, х2, … , хп; z1, z2, … , zk;
…
ym = mх1, х2, … , хп; z1, z2, … , zk.

Эта модель называется булевым автоматом. Ее также можно представить в компактной векторной форме:

z+ = х, z;
y = х, z.

Булев автомат в определенном смысле ближе к реальным дискретным устройствам, поскольку его переменные непосредственно реализуются физическими переменными устройства, в частности, на типичных для современной техники элементах с двумя устойчивыми состояниями. Векторы х, у и z показывают структуру абстрактных символов а и b и состояния q. Приведенная выше система функций соответствует структуре, изображенной на рис. 18.2, где КС – комбинационная схема, реализующая приведенную выше систему, а П – блок памяти, осуществляющий задержку на период между соседними моментами времени.
Переменная zi представляет состояние i-го двоичного элемента памяти, а выражение

zi+ = iх1, х2, … , хп; z1, z2, … , zk

Еще одним способом представления автомата является матрица поведения, представляющая собой квадратную матрицу, строки и столбцы которой помечаются состояниями автомата. В случае автомата Мура на пересечении строки qi и столбца qj матрицы поведения записываются входные символы, переводящие автомат из состояния qi в состояние qj, а строки помечаются также и выходными символами. В случае автомата Мили элементы матрицы поведения, кроме входных символов, вызывающих соответствующие переходы, содержат выходные символы, которые сопровождают эти переходы. Если из состояния qi нет перехода в состояние qj, то на пересечении строки qi и столбца qj ставится прочерк. Для рассмотренных автоматов ниже представлены матрицы поведения, причем первая из них – матрица поведения автомата Мура, вторая – матрица поведения автомата Мили.

,

.

Автомат Мура представляется одной таблицей переходов, к которой добавлен один столбец со значениями функции выходов (табл. 18.4).

Можно свести таблицу переходов и таблицу выходов автомата Мили в одну таблицу, которую называют таблицей переходов и выходов. Такая таблица для автомата, заданного в виде табл. 18.2 и табл. 18.3, имеет вид табл. 18.5.

Более наглядным при небольшом числе состояний является представление автомата в виде графа поведения автомата, который представляет собой ориентированный граф. Его вершины соответствуют состояниям автомата, а дуги – переходам между состояниями. При этом дуга помечается всеми входными символами, которые вызывают соответствующий переход, и выходными символами, сопровождающими данный переход (в случае автомата Мили). В случае автомата Мура выходными символами помечаются вершины, соответствующие состояниям, в которых находится автомат при выдаче данных символов. На рис. 18.1 изображены графы переходов автоматов, заданных табл. 18.4 и 18.5.
Таблица 18.4 Таблица 18.5
Таблица переходов автомата Мура Таблица переходов и выходов
автомата Мили
a1 a2 a3 a4  a1 a2 a3 a4
q1 q1 q2 q1 q2 b1 q1 q1,b1 q2,b1 q1,b2 q2,b1
q2 q3 q1 q3 q1 b1 q2 q3,b1 q1,b2 q3,b2 q1,b1
q3 q3 q1 q1 q1 b2 q3 q3,b2 q1,b2 q1,b1 q1,b1


a1, a3 a1/b1, a3/b2

q1, b1
a2/b1, a4/b1 q1 a2/b2, a3/b1, a4/b1

a2, a4 a2, a3, a4
a2, a4 a2/b2, a4/b1 a1/b2
a1

q2, b1 a1, а3 q3, b2 q2 a1/b1, а3/b2 q3
а) б)
Рис. 18.1. Примеры графов поведения: а) автомата Мура; б) автомата Мили

Конечный автомат удобно представлять таблицей переходов и таблицей выходов. Строкам этих таблиц соответствуют состояния автомата, столбцам – входные символы. На пересечении строки, соответствующей состоянию q, и столбца, соответствующего входному символу а, в таблице переходов записывается значение (a, q), а в таблице выходов – значение (a, q). Другими словами, в первом случае в клетке таблицы указывается состояние, в которое автомат переходит из состояния q при поступлении на его вход символа а, а во втором случае – выходной символ, который при этом выдает автомат. Табл.18.2 и табл.18.3 представляют собой пример описанного представления автомата Мили, у которого А = {a1, a2, a3, a4}, В = {b1, b2} и Q {q1, q2, q3}.
Таблица 18.2 Таблица 18.3
Функция Функция
a1 a2 a3 a4 a1 a2 a3 a4
q1 q1 q2 q1 q2 q1 b1 b1 b2 b1
q2 q3 q1 q3 q1 q2 b1 b2 b2 b1
q3 q3 q1 q1 q1 q3 b2 b2 b1 b1

Зная начальное состояние автомата и входную последовательность, нетрудно получить по этим таблицам соответствующую последовательность выходных символов. Приведем пример такого соответствия для автомата, заданного табл. 18.2 и 18.3, на вход которого поступила последовательность символов а1, а2, а2, а1, а3, а4, а1, а4 при начальном состоянии q1. Покажем также состояния, которые проходит автомат:

а1 а2 а2 а1 а3 а4 а1 а4
q1 q1 q2 q1 q1 q1 q2 q3
b1 b1 b2 b1 b2 b1 b1 b1.

Конечный автомат является абстрактной математической моделью дискретного устройства. Поведение, описанное данной моделью, может быть по-разному реализовано в дискретном устройстве. При синхронной реализации моменты времени, когда определяется состояние, в которое переходит устройство, а в случае автомата Мили и выходной символ, зафиксированы. Технически это осуществляется введением генератора синхронизирующих сигналов, которые инициируют соответствующие действия. Период следования таких сигналов не должен быть меньше чем время, необходимое для завершения переходных процессов в устройстве. Реализованный таким образом конечный автомат называется синхронным автоматом.
При асинхронной реализации указанные моменты времени не фиксированы. Они связаны с моментами, в которые происходит изменение входного сигнала. Реализованный таким образом автомат называется асинхронным автоматом. Если синхронный автомат различает последовательности разной длины из одинаковых входных символов, т. е. может реагировать на них различными выходными последовательностями, то асинхронный автомат воспринимает последовательность одинаковых входных символов любой длины как один символ. В схеме такого устройства генератор синхронизирующих сигналов отсутствует.