Основные определения теории автоматов

Конечным автоматом (просто автоматом) называется система (пятерка) [19]:

S=< X, Y, Z, j, y>,

в которой Х={х₁, х₂,..., х_i} – конечное входное множество (входной алфавит); Y={y₁, y₂,..., y_j} – конечное множество внутренних состояний автомата (алфавит состояний); Z={z₁, z₂,..., z_k} – конечное выходное множество (выходной алфавит); j – функция переходов (из состояния в другие состояния); y – функция выходов.

Если указанные множества бесконечные, то это уже не конечный автомат, но может быть дискретный автомат.

Если функция переходов – вероятностная, то это недетерминированный автомат.

Если в автомате выделено одно состояние, называемое начальным (обычно это y₁), то полученный автомат называется инициальным и обозначается < S, y>. Таким образом, по неинициальному автомату с i состояниями можно i различными способами определить инициальный автомат.

Функция переходов представляет собой отображение вида j: или в другом виде:

y(t+1)=j[x(t), y(t)],

где x(t), y(t), y(t+1) – конкретные символы алфавитов Х и Y соответственно в моменты автоматного времени t, t+1 (в тактах t и t+1); y(t) называется текущим внутренним состоянием при соответствующем х(t), а y(t+1) – последующим внутренним состоянием.

Иначе говоря, функция переходов определяет последующее состояние автомата по заданному текущему и входному символу.

Функция выходов представляет собой отображение вида y: Х´ Y®Z или в другом виде:

z(t)=y[x(t), y(t)],

где x(t), y(t), z(t) – конкретные символы алфавитов X, Y, Z соответственно. Мы не будем особо выделять последующие значения x(t+1) и z(t+1), поэтому зависимость от t будем указывать только для внутреннего состояния, чтобы отделять y(t) от y(t+1).

Указанная функция выходов – функция так называемого автомата Мили.

В теории конечных автоматов рассматривается также автомат Мура, у которого функция выходов проще: y: или z(t)=y[y(t)].

Автомат называется комбинационным, если для любого входного символа х и любых состояний y_i, y_j j(х, y_i)=j(х, y_j)=z, иначе говоря, если выходной символ z не зависит от состояния и определяется текущим входным символом. Говорят, что у такого частного класса автомата все состояния эквивалентны и, следовательно, комбинационный автомат имеет одно состояние. Такой автомат задается тройкой:

S=< X, Z, y>.

Рассмотрим представление конечного автомата в виде «черного» ящика (рис. 51).

Рис. 51. Конечный автомат (КА) в виде «черного» ящика

В комбинационном автомате внутренних состояний не указывают.

Входное слово – последовательность входных символов.

Выходное слово – последовательность выходных символов, соответствующих входному слову. В конечном автомате также выделяется последовательность символов внутренних состояний, соответствующих входному слову.

Большой вклад в теорию дискретных (цифровых) автоматов внесли отечественные ученые: М.А. Гаврилов, который опубликовал первую в мире монографию «Теория релейно-контактных схем» (1950 г.), В.М. Глушков, В.Н. Рогинский, П.П. Пархоменко, В.Г. Лазарев, С.И. Баранов, А.Д. Закревский, Э.А. Якубайтис, С.В. Яблонский, В.И. Варшавский и др.

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

Поскольку функции 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

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

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

Таблица 52

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

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

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

Рассмотрим последовательностный автомат, заданный табл. 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={х}. Все входные слова автономного автомата имеют вид хх...х.