Описание конечных детерминированных автоматов

таблицами переходов-выходов и графами

 

Поскольку функции j и y определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводят в одну таблицу j´y:  и называют таблицей переходов-выходов или просто таблицей переходов (автоматной таблицей). При задании автомата ориентированным графом (орграфом), его вершины сопоставляют с внутренними состояниями, и дуги – с условиями перехода из состояния в состояние. Дуги помечают входными символами автомата. Дуги также помечают и соответствующими выходными символами, если это автомат Мили.

Рассмотрим граф переходов некоторого автомата Мили (рис. 52), Х={x₁,x₂}, Y={y₁,y₂,y₃}, Z={z₁,z₂,z₃}.

На графе автомата Мили (рис. 52) дуги помечаются дробью, где в числителе – входной символ, в знаменателе – выходной символ.

Представим этот же автомат Мили таблицей переходов (табл. 50).

 

Рис. 52. Граф некоторого автомата Мили

Таблица 50

Таблица переходов выходов автомата Мили, заданного графом рис. 52

Внутреннее состояние	Входной символ
y(t)	х1	х2
y1
y2
y3		-

 

В клетках табл. 50 записывается дробь, в числителе которой указывается последующее внутреннее состояние y(t+1), а в знаменателе – выходной символ z(t). Это указано в специальной выноске таблицы (). Видно, что автомат не полностью определенный (клетка y₃х₂ не заполнена).

Рассмотрим граф некоторого автомата Мура (рис. 53), Х={x₁,x₂}, Y={y₁,y₂,y₃}, Z={z₁,z₂,z₃}:

 

 

Рис. 53. Граф некоторого автомата Мура

 

Выходные символы в автомате Мура сопоставляются с конкретными внутренними состояниями и записываются в знаменателе дроби, помечающей внутренние состояния. Само внутреннее состояние указывается в числителе. Дуги графа автомата Мура помечаются только входными символами. Соответствующая этому автомату Мура таблица переходов представлена табл. 51.

Таблица 51

Таблица переходов-выходов автомата Мура, заданного графом рис. 53

Внутреннее состояние	Входной символ		Выходной символ
y(t)	х1	х2
y1	y3	y1	z2
y2	y1	y3	z1
y3	y1	-	z3
		y(t+1)

 

В клетках табл. 51, соответствующих входным символам, записывается только последующее внутреннее состояние y(t+1), что указано в специальной сноске (y(t+1)).

Комбинационный автомат задается таблицей истинности (соответствия), уже известной нам, так как граф переходов такого автомата имеет одну вершину и m петель, где m – число входных символов. Пример таблицы истинности, задающей некоторый комбинационный автомат, приведен табл. 52.

Таблица 52

Таблица истинности комбинационного автомата:

Х={x₁,x₂,х₃,х₄}, Z={z₁,z₂,z₃,z₄}

Входной символ х	Выходной символ z
x1	z2
x2	z4
x3	z1
x4	z3

 

В отличие от комбинационного конечного автомата, имеющего одно внутреннее состояние, конечные автоматы, имеющие больше, чем одно внутреннее состояние, называются последовательностными конечными автоматами или просто последовательностными автоматами.

Рассмотрим последовательностный автомат, заданный табл. 53. Зафиксируем начальное состояние y₁ и каждому входному слову (последовательности входных символов) a=x_j1x_j2...x_jr поставим в соответствие слово w в выходном алфавите:

w=y(x_j1,y₁)y(x_j1,x_j2,y₁)... y(x_j1,...,x_jr,y₁).

Это соответствие, отображающее входные слова в выходные, называется автоматным отображением.

Таблица 53

Таблица переходов-выходов некоторого автомата Мили

Зададим входное слово a=x₁х₂х₃х₄.

Тогда выходное слово w=z₁z₁z₁z₃.

Рассмотрим подробнее процесс формирования выходного слова:

В этой последовательности указаны так называемые переходы из состояния в состояние, обведенные линией. То есть, например, при поступлении х₂ автомат сначала находится в состоянии y₁, а затем автомат переходит в состояние y₂. Указанные выше последовательности иногда изображают стрелками в таблице переходов-выходов.

Состояния y_j называют достижимыми из состояния y_i, если существует входное слово a, такое, что j(a,y_i)=y_j.

Состояния называются эквивалентными, если они соответствуют одинаковым последовательностям «входное слово – выходное слово»; причем длина такой последовательности может быть любая ³1. Например, в последовательности:

состояния y₁ и y₉ эквивалентны (длина последовательности =1), состояния y₃ и y₇ неэквивалентны, поскольку последовательность длиной 2: в первом случае , а во втором – .

Таким образом, состояние y₉ заменяется на состояние y₁.

В последовательности:

состояния y₁,у₅,y₉ также эквивалентны. Эквивалентны состояния y₃ и y₇, а также состояния y₄,y₈. Одинаковые последовательности обведены.

В этих примерах предполагается, что далее последовательности повторяются, т.е. после y₉ следует y₂,y₃ и т.д.

Таким образом, вторую последовательность можно представить в виде:

x₁ x₂ x₃ x₂ x₁ x₄ x₃ x₂ x₁

y₁ y₂ y₃ y₄ y₁ y₅ y₃ y₄ y₁

z₁ z₁ z₂ z₃ z₁ z₂ z₂ z₃ z₁

где y₉ заменено на y₁, y₇ на y₃, y₈ на y₄.

Автомат, реализующий эту последовательность, эквивалентен автомату, реализующему исходную последовательность, но имеет меньше состояний.

Автомат называется сильно связанным, если из любого его состояния достижимо любое другое состояние.

Автомат называется автономным, если его входной алфавит состоит из одной буквы X={х}. Все входные слова автономного автомата имеют вид хх...х.