30. Описание конечных автоматов таблицами переходов-выходов и графами

Поскольку функции  и  определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводят в одну таблицу :   и называют таблицей переходов-выходов или просто таблицей переходов (автоматной таблицей). При задании автомата ориентированным графом (орграфом), его вершины сопоставляют с внутренними состояниями, и дуги – с условиями перехода из состояния в состояние. Дуги помечают входными символами автомата. Дуги также помечают и соответствующими выходными символами, если это автомат Мили.
Рассмотрим граф переходов некоторого автомата Мили (рис. 52), Х={x1,x2}, Y={y1,y2,y3}, Z={z1,z2,z3}.
На графе автомата Мили (рис. 52) дуги помечаются дробью, где в числителе – входной символ, в знаменателе – выходной символ.
Представим этот же автомат Мили таблицей переходов (табл. 50).

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

Таблица переходов выходов автомата Мили, заданного графом рис. 52
http://i078.radikal.ru/1105/23/40e4b5488570.jpg
Внутреннее
состояние Входной
символ
y(t) х1 х2
y1

y2

y3
-

В клетках табл. 50 записывается дробь, в числителе которой указывается последующее внутреннее состояние y(t+1), а в знаменателе – выходной символ z(t). Это указано в специальной выноске таблицы ( ). Видно, что автомат не полностью определенный (клетка y3х2 не заполнена).
Рассмотрим граф некоторого автомата Мура (рис. 53), Х={x1,x2}, Y={y1,y2,y3}, Z={z1,z2,z3}:

Рис. 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
Таблица истинности комбинационного автомата:
Х={x1,x2,х3,х4}, Z={z1,z2,z3,z4}
Входной
символ
х Выходной
символ
z
x1 z2
x2 z4
x3 z1
x4 z3

В отличие от комбинационного конечного автомата, имеющего одно внутреннее состояние, конечные автоматы, имеющие больше, чем одно внутреннее состояние, называются последовательностными конечными автоматами или просто последовательностными автоматами.
Рассмотрим последовательностный автомат, заданный табл. 53. Зафиксируем начальное состояние y1 и каждому входному слову (последовательности входных символов) =xj1xj2...xjr поставим в соответствие слово  в выходном алфавите:
=(xj1,y1)(xj1,xj2,y1)... (xj1,...,xjr,y1).
Это соответствие, отображающее входные слова в выходные, называ-ется автоматным отображением.
Таблица 53
Таблица переходов-выходов некоторого автомата Мили

Зададим входное слово =x1х2х3х4.
Тогда выходное слово =z1z1z1z3.
Рассмотрим подробнее процесс формирования выходного слова:

В этой последовательности указаны так называемые переходы из со-стояния в состояние, обведенные линией. То есть, например, при поступ-лении х2 автомат сначала находится в состоянии y1, а затем автомат переходит в состояние y2. Указанные выше последовательности иногда изображают стрелками в таблице переходов-выходов.
Состояния yj называют достижимыми из состояния yi, если существу-ет входное слово , такое, что (,yi)=yj.

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

состояния y1 и y9 эквивалентны (длина последовательности =1), состоя-ния y3 и y7 неэквивалентны, поскольку последовательность длиной 2: в первом случае  , а во втором –  .
Таким образом, состояние y9 заменяется на состояние y1.
В последовательности:

состояния y1,у5,y9 также эквивалентны. Эквивалентны состояния y3 и y7, а также состояния y4,y8. Одинаковые последовательности обведены.
В этих примерах предполагается, что далее последовательности повторяются, т.е. после y9 следует y2,y3 и т.д.
Таким образом, вторую последовательность можно представить в виде:
x1 x2 x3 x2 x1 x4 x3 x2 x1
y1 y2 y3 y4 y1 y5 y3 y4 y1
z1 z1 z2 z3 z1 z2 z2 z3 z1
где y9 заменено на y1, y7 на y3, y8 на y4.
Автомат, реализующий эту последовательность, эквивалентен автомату, реализующему исходную последовательность, но имеет меньше состояний.
Автомат называется сильно связанным, если из любого его состояния достижимо любое другое состояние.
Автомат называется автономным, если его входной алфавит состоит из одной буквы X={х}. Все входные слова автономного автомата имеют вид хх...х.