МПС

Способы задания автомата (Лекция)

ПЛАН ЛЕКЦИИ

1. Табличный способ

2. Графический способ задания автомата

 

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d, l} , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l. При этом среди множества A = {a₀,a₁,…, a_n} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

 

2. Табличный способ

При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Таблица переходов

 

Таблица выходов

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца a_i и строки x_j в таблице переходов ставится состояние a_s = d[ a_i,x_j], в которое автомат перейдет из состояния a_i под воздействием сигнала x_j; а в таблице выходов – соответствующий этому переходу выходной сигнал y_g = l[ a_i,x_j].

 

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

 

Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но и также все три алфавита: входной, выходной и алфавит состояний.

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

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

 

Автомат Мили

 

Автомат Мура

 

В этой таблице каждому столбцу приписан, кроме состояния a_i, еще и выходной сигнал y(t) = l(a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

Приведем примеры табличного задания автоматов Мили и Мура:

 

По этим таблицам можно найти реакцию автомата на любое входное слово. Например.

Для автомата Мили:                           Для автомата Мура:

x₁x₂x₂x₂x₁…                                        x₁x₂x₂x₂x₁…

a₀a₁a₀a₀a₀a₁                                                    a₀a₂a₄a₁a₄

y₁y₁y₂y₂y₁                                                       y₂y₁y₂y₁y₂

 

 

2. Графический способ задания автомата (задание автомата с помощью графа)

 

Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a_i и a_s соединяются дугой, направленной от a_i к a_s, если в автомате имеется переход из a_i в a_s, т.е. a_s =  d(a_i, x_j). В автомате Мили дуга отмечается входным сигналом x_j, вызвавшим переход, и выходным сигналом y_g, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

 

а)                                                        б)