Табличный способ задания автомата

Автомат Мура задается отмеченной таблицей переходов и выходов. Автомат Мили задается либо совмещенной таблицей переходов и выходов, либо двумя таблицами – таблицей переходов и таблицей выходов. Во всех таблицах строки соответствуют входным сигналам, а столбцы – состояниям. Автомат, заданный табличным способом, всегда детерминирован.

В отмеченной таблице переходов автомата Мура каждый столбец отмечается выходным сигналом. Кроме того, на пересечении строки x_i и столбца a_j записывается состояние a_k, в которое перейдет автомат, находящийся в состоянии a_j под действием входного сигнала x_i, т. е. δ(a_j, x_i) = a_k.

Рассмотрим пример табличного задания автомата Мура (табл. 1.1). Пусть автомат Мура имеет три входных сигнала, два выходных сигнала и три состояния.

X = {x₁, x₂, x₃}; A = {a₀, a₁, a₂}; Y = {y₁, y₂}. (1.32)

Таблица 1.1

Отмеченная таблица автомата Мура

δ: (A × X) → A, λ: A→ Y

Данный автомат является полностью определенным.

Рассмотрим пример табличного задания автомата Мили. Пусть автомат Мили имеет два входных сигнала, три выходных сигнала и три состояния.

X = {x₁, x₂, x₃}; A = {a₀, a₁, a₂}; Y = {y₁, y₁, y₃,}. (1.33)

В клетку таблицы переходов автомата Мили (табл. 1.2) на пересечении строки х_i и столбца a_j записывается состояние, в которое перейдет автомат, а в соответствующую клетку таблицы выходов (табл. 1.3) – выходной сигнал, который автомат выдает на этом переходе.

Таблица 1.2 Таблица переходов автомата Мили δ: (A × X) → A	Таблица 1.3 Таблица выходов автомата Мили λ: (A × X) → Y
а х	а0	а1	а2		а х	а0	а1	а2
х1	а1	а0	а1		х1	y1	y2	–
х2	а0	а2	а1		х2	y1	y3	y2
					«–» – значение не определено

Например, δ(а₁, х₁) = а₀ означает, что автомат, находясь в состоянии а₁ при поступлении на вход сигнала х₁, перейдет в состояние а₀; λ(а₁, х₁) = y₂ означает, что автомат, находясь в состоянии а₁ при поступлении на вход сигнала х₁, выдаст выходной сигнал y₂; λ(а₁, х₂) = y₃ означает, что автомат, находясь в состоянии а₁ при поступлении сигнала х₂, выдает выходной сигнал y₃. Таким образом, находясь в одном и том же состоянии, автомат Мили может выдавать различные сигналы.

В этом случае совмещенная таблица переходов и выходов автомата Мили имеет следующий вид (табл. 1.4).

Таблица 1.4

Совмещенная таблица переходов и выходов автомата Мили

δ: (A × X) → A, λ: (A × X) → Y

В клетку совмещенной таблицы переходов и выходов автомата Мили на пересечении строки х_i и столбца a_j записывается состояние, в которое перейдет автомат, а через косую черту – выходной сигнал, который автомат выдает на этом переходе.

Табличный способ обладает невысокой наглядностью, однако автомат, заданный табличным способом, всегда детерминирован. Кроме того, табличное задание автомата позволяет легко перейти к процессу структурного синтеза. Для этого часто используется прямая таблица переходов и выходов автомата.

Рассмотрим пример задания автомата Мура прямой таблицей переходов и выходов. Пусть автомат Мура имеет два входных сигнала, три выходных сигнала и три состояния.

X = {x₁, x₂}; A = {a₀, a₁, a₂}; Y = {y₁, y₂, y₃}. (1.34)

При комбинации (а₁, x₂) не определены функция переходов d = y(а₁) и функция выходов l = j(а₁), см. табл. 1.5.

Таблица 1.5

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

δ: (A × X) → A, λ: A→ Y

В процессе структурного синтеза на основе данной таблицы строится кодированная прямая таблица переходов и выходов автомата (табл. 1.6). При этом столбец 3 будет представлять собой исходные данные для формирования функции возбуждения элементов памяти автомата, имеющей различный вид при реализации памяти автомата на D-триггерах и на JK-триггерах.

Коды состояний в табл. 1.6 представлены в двоичном формате при помощи позиционного двоичного кода с использованием естественного способа кодирования. Входные и выходные сигналы могут быть закодированы в двоичном формате как с использованием унитарного кодирования, так и с использованием кодирования при помощи позиционного двоичного кода.

Таблица 1.6

Прямая кодированная таблица переходов и выходов автомата Мили

δ: (A × X) → A, λ: (A × X) → Y