7.2. Представления автомата

Конечный автомат удобно представлять таблицей переходов и таблицей выходов. Строкам этих таблиц соответствуют состояния автомата, столбцам – входные символы. На пересечении строки, соответствующей состоянию q, и столбца, соответствующего входному символу а, в таблице переходов записывается значение (a, q), а в таблице выходов – значение (a, q). Другими словами, в первом случае в клетке таблицы указывается состояние, в которое автомат переходит из состояния q при поступлении на его вход символа а, а во втором случае – выходной символ, который при этом выдает автомат. Табл.7.2 и табл.7.3 представляют собой пример описанного представления автомата Мили, у которого А = {a₁, a₂, a₃, a₄}, В = {b₁, b₂} и Q  {q₁, q₂, q₃}.

Таблица 7.2    Таблица 7.3

Функция  Функция 

Зная начальное состояние автомата и входную последовательность, нетрудно получить по этим таблицам соответствующую последовательность выходных символов. Приведем пример такого соответствия для автомата, заданного табл. 7.2 и 7.3, на вход которого поступила последовательность символов а₁, а₂, а₂, а₁, а₃, а₄, а₁, а₄ при начальном состоянии q₁. Покажем также состояния, которые проходит автомат:

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

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

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

Более наглядным при небольшом числе состояний является представление автомата в виде графа поведения автомата, который представляет собой ориентированный граф. Его вершины соответствуют состояниям автомата, а дуги – переходам между состояниями. При этом дуга помечается всеми входными символами, которые вызывают соответствующий переход, и выходными символами, сопровождающими данный переход (в случае автомата Мили). В случае автомата Мура выходными символами помечаются вершины, соответствующие состояниям, в которых находится автомат при выдаче данных символов. На рис. 7.1 изображены графы переходов автоматов, заданных табл. 7.4 и 7.5.

 Таблица 7.4 Таблица 7.5

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

автомата Мили

a₁, a₃

q₁

a₂/b₂, a₃/b₁, a₄/b₁

a₂, a₄

a₁

q₂, b₁

а) б)

Рис. 7.1. Примеры графов поведения: а) автомата Мура; б) автомата Мили

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

,

.