Введение в теорию конечных автоматов

В вычислительной технике используются системы двух классов: -Комбинационные системы Особенности: имеют функциональную зависимость между входными и выходными сигналами y(t)=f(x(t), не имеют элементов памяти. -Цифровые автоматы (схемы второго класса или просто автоматы) Особенности: содержат в своем составе запоминающие элементы, выходные сигналы зависят не только от входных(в один и тот же момент времени), но и от состояния схемы, которое зависит от поступивших в предыдущие моменты времени входных сигналов. Автомат-это дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать различные выходные сигналы

Математической моделью конечного автомата является абстрактный автомат, с одним входным и выходным каналом: X(x 1, …, x F )--->A(a 0,..., a M )--->Y(y 1, …, y G ) Автомат функционирует в дискретные моменты времени, интервал между которыми Т (такт). В каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (Tconst).

Детерминированные автоматы Для задания конечного автомата S необходима совокупность из пяти объектов: S{A, X, Y, d, l} A = {a 0, a 1, a 2,..., a m,..., a M } – множество состояний автомата, X = {x 1, x 2, …, x f,…, x F } – множество входных сигналов или входной алфавит, Y = {y 1, y 2, …, y g,…, y G } – множество выходных сигналов или выходной алфавит, d – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = d [a(t), x(t)], l – функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е. y(t) = l[a(t), x(t)]. Для того, чтобы автомат был конечным необходимо чтобы множества A, X, Y были конечны

Принцип работы детерминированного автомата: В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a 0. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал: y(t) = l[a(t), x(t)] и переходит в состояние: a(t + 1) = d[a(t), x(t)] Таким образом: Детерминированными называют автоматы, которые каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t + 1) и y(t)

Преобразование информации в детерминированных автоматах 1. Любое входное слово длиною l букв преобразуется в выходное слово той же длины. 2. Если каждый раз перед подачей входных сигналов автомат находится в одном и том же состоянии, то при совпадении в двух входных словах первых l 1 букв, в выходных словах первые l 1 букв также совпадут. Кроме детерминированных автоматов существуют вероятностные автоматы, в которых переход из одного состояния в другое под воздействием случайных или детерминированных входных сигналов происходит случайно. Работа таких автоматов описывается уже матрицей переходов d, элементами которой являются вероятности переходов из одного состояния в другое.

Автоматы Мили и Мура Применяемые на практике автоматы принято разделять на два класса – это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать Автомат Мили конечный автомат, выходные сигналы которого зависят как от состояния автомата, так и от значения входного сигнала Закон функционирования автомата Мили a(t + 1) = d [a(t), x(t)], y(t) = l[a(t), x(t)]

Автомат Мура- конечный автомат, входные сигналы которого y(t) в каждый дискретный момент времени t однозначно определяется состоянием автомата в тот же момент времени и не зависят от входного сигнала a(t + 1) = d [a(t), x(t)], y(t) = l[a(t)].

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

Табличный способ При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов: Таблица переходов Таблица выходов x j / a 1 a0a0 …aMaM x1x1 d(a 0, x 1 )…d(a M, x 1 ) …… … … xFxF d(a 0, x F )…d(a M, x F ) x j / a 1 a0a0 …aMaM x1x1 l(a 0, x 1 )…l(a M, x 1 ) …… … … xFxF l(a 0, x F )…l(a M, x F )

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца a i и строки x j в таблице переходов ставится состояние as = d[ a i, x j ], в которое автомат перейдет из состояния a i под воздействием сигнала x j, а в таблице выходов – соответствующий этому переходу выходной сигнал yg = l[a i, x j ]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов: x j / a 1 x j / a 1 a0a0 …aMaM x1x1 d(a 0, x 1 ) / l(a 0, x 1 ) … d(a M, x 1 ) / l(a M, x 1 ) ………… xFxF d(a 0, x F ) / l(a 0, x F ) … d(a M, x F ) / l(a M, x F )

Так как в автомате Мура выходной сигнал однозначно определяется состоянием автомата, то для его задания требуется только одна таблица, которая называется отмеченной таблицей переходов автомата Мура: В этой таблице каждому столбцу приписан, кроме состояния a i, еще и выходной сигнал y(t) = l(a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом. ygyg l(a 0 )…l(a M ) x j / a 1 a0a0 …aMaM x1x1 d(a 0, x 1 )…d(a M, x 1 ) ………… xFxF d(a 0, x F )…d(a M, x F )

Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но также и все три алфавита: входной, выходной и алфавит состояний. Рассмотрим примеры табличного задания автоматов Мили и Мура: Автомат Мура: Автомат Мили:. ygyg y2y2 y1y1 y1y1 y3y3 y2y2 x j / a i a0a0 a1a1 a2a2 a3a3 a4a4 x1x1 a2a2 a1a1 a3a3 a4a4 a2a2 x2x2 a3a3 a4a4 a4a4 a0a0 a1a1 a0a0 a1a1 a2a2 a3a3 x1x1 a 1 / y 1 a 2 / y 3 a 3 / y 2 a 0 / y 1 x2x2 a 0 /y 2 a 0 / y 1 a 3 / y 1 a 2 / y 3

По этим таблицам можно найти реакцию автомата на любое входное слово. Для автомата Мура: x 1 x 2 x 2 x 2 x 1 a 0 a 2 a 4 a 1 a 4 y 2 y 1 y 2 y 1 y 2 Для автомата Мили: x 1 x 2 x 2 x 2 x 1 a 0 a 1 a 0 a 0 a 0 a 1 y 1 y 1 y 2 y 2 y 1

Графический способ Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a i и a s соединяются дугой, направленной от a i к a s, если в автомате имеется переход из a i в a s, то есть a s = d(a i, x j ). В автомате Мили (рис. 4.2) дуга отмечается входным сигналом x j, под действием которого происходит этот переход, и выходным сигналом y g, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние автомата. В автомате Мура (рис. 4.3) в вершинах графа кроме состояния автомата отмечается соответствующий выходной сигнал, а дуга отмечается только входным сигналом x j, под действием которого происходит этот переход.

Преобразование автомата Мили в автомат Мура Граф автомата Мили имеет вид: В автомате Мили X a = {x 1, x 2 }, Y a = {y 1, y 2 }, A a = {a 0, a 1, a 2 }. В эквивалентном автомате Мура X b = X a = {x 1, x 2 }, Y b = Y a = {y 1, y 2 } Построим множество состояний A b автомата Мура, для чего найдем множества пар, порождаемых каждым состоянием автомата S a.

Состояние Порождаемые пары a 0 {(a 0, y 1 ), (a 0, y 2 )} = {b 1, b 2 } a 1 {(a 1, y 1 )} = {b 3 } a 2 {(a 2, y 1 ), (a 2, y 2 )} = {b 4, b 5 } Отсюда имеем множества A b состояний автомата Мура A b = {b 1, b 2, b 3, b 4, b 5 }. Для нахождения функции выходов l b с каждым состоянием, представляющим собой пару вида (a i, y g ), отождествим выходной сигнал, являющийся вторым элементом этой пары. В результате имеем: l b (b 1 ) = l b (b 3 ) = l b (b 4 ) = y 1 ; l b (b 2 ) = l b (b 5 ) = y 2.

Построим функцию переходов d b. Так как в автомате S a из состояния a 0 есть переход под действием сигнала x 1 в состояние a 2 с выдачей y 1,то из множества состояний {b 1, b 2 }, порождаемых a 0, в автомате S b должен быть переход в состояние (a 2, y 1 ) = b 4 под действием сигнала x 1. Аналогично, из {b 1, b 2 } под действием x 2 должен быть переход в (a 0, y 1 ) = b 1. Из (a 1, y 1 ) = b 3 под действием x 1 переход в (a 0, y 1 ) = b 1, а под действием x 2 – в (a 2, y 2 ) = b 5. Наконец из состояний {(a 2, y 1 ), (a 2, y 2 )} = {b 4, b 5 } под действием x 1 в (a 0, y 2 ) = b 2, а под действием x 2 – в (a 1, y 1 ) = b 3. В результате имеем граф (рис. 7.11) и таблицу переходов эквивалентного автомата Мура.

Граф эквивалентного автомата Мура

В качестве начального состояния автомата S b можно взять любое из состояний b 1 или b 2, так как оба порождены состоянием a 0 автомата S a. ygyg y1y1 y2y2 y1y1 y1y1 y2y2 x j \b j b1b1 b2b2 b3b3 b4b4 b5b5 x1x1 b4b4 b4b4 b1b1 b2b2 b2b2 x2x2 b1b1 b1b1 b5b5 b3b3 b3b3

Переход от автомата Мура к автомату Мили Пусть дан автомат Мура S b ={A b, X b, Y b, d b, l b }. Необходимо построить эквивалентный ему автомат Мили S a = {A a, X a, Y a, d a, l a }. По определению эквивалентности имеем X a = X b ; Y a = Y b. Кроме того, A a = A b, d a = d b. Остается только построить функцию выходов. Если в автомате Мура d b (a i, x j ) = a s, а l b (a s ) = y g, то в автомате Мили l a (a i, x j ) = y g. Другими словами: l(a i, x j ) = l b (d b (a i, x j )). Таким образом, таблица переходов автоматов Мили и Мура совпадают. А таблица выходов эквивалентного автомата Мили строится так, что в каждую клетку таблицы записывается выходной сигнал, которым отмечено состояние, расположенное в данной клетке.

Дан автомат Мура Тогда эквивалентный ему автомат Мили имеет следующую совмещенную таблицу переходов и выходов: x j \y i y1y1 y1y1 y3y3 y2y2 y3y3 x j \a i a0a0 a1a1 a2a2 a3a3 a4a4 x1x1 a1a1 a4a4 a4a4 a2a2 a2a2 x2x2 a3a3 a1a1 a1a1 a0a0 a0a0 a0a0 a1a1 a2a2 a3a3 a4a4 x1x1 a 1 \ y 1 a 4 \ y 3 a 2 \ y 3 x2x2 a 3 \ y 2 a 1 \ y 1 a 0 \ y 1