Лекция Конечные автоматы. Автоматы мура и Мили

где

 – функция переходов автомата из одного состояния в другое:

 – функция выхода,

_ - начальное состояние автомата.

Рисунок 1. Представление абстрактного автомата

Абстрактный автомат (АА) можно рассматривать как "черный ящик" с одним входом и одним выходом, с которым можно экспериментировать, не зная, что находится внутри.

Рисунок 2. Преобразование входных слов в выходные

На практике широкое распространение получили две основные модели, описывающие функционирование АА:

1. Модель Мили;

2. Модель Мура.

В зависимости от законов функционирования различают автоматы:

1. Автоматы первого рода, или автоматы Мили:

a(t+1)=  (a(t),x(t))

y(t)=(a(t),x(t))

t – текущий момент времени; t+1 – следующий момент времени; а(t+1) – состояние автомата в следующий момент времени; a(t), x(t), y(t) – элементы описания автомата в текущий момент времени.

2. Правильные автоматы второго рода, или автоматы Мура:

a(t+1)= (a(t),x(t))

y(t)=(a(t))

В модели Мура выходной сигнал явно зависит только от состояния, а косвенно – и от входного сигнала. Любой автомат можно спроектировать по той или иной модели

Рассмотри два основных способов задания автоматов:

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

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

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

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

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

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

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

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

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

Автомат Мили

Автомат Мура

В этой таблице каждому столбцу приписан, кроме состояния a_i, еще и выходной сигнал y(t) = (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₂

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

а) б)