Раздел 3. Конечные автоматы .

Понятие о конечных автоматах различного типа.

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

Для обеих задач удобно переменные, которые характеризуют систему, представлять следующим образом:

· входные переменные, которые влияют на поведение системы;

· выходные переменные реакции, представляющие величины, характеризующие поведение системы;

· внутренние переменные (состояния) системы.

Схематически система может быть представлена “Черным ящиком”, о внутреннем устройстве которого ничего не известно.

 

Рис.3.1. Представление системы в виде “черного ящика”.

Рис.3.1. Иллюстрирует представление системы в виде черного ящика, когда она имеет n и m выходных переменных.

Предполагается, что рассматриваемая система с конечным числом состояний управляется некоторым независимым синхронизирующим источником. Все переменные системы изменяются не непрерывно,а только в дискретные моменты времени, в которые на систему поступает синхронизирующий сигнал. Эти моменты времени называются тактовыми моментами или просто тактами. Следует отметить, что какой бы ни был интервал времени между тактами и какие бы ни были изменения системы внутри этого такта, значения переменных в i-ый тактовый момент зависят только от номера i и не зависят от текущего значения времени ti.

Система, удовлетворяющая изложенным предположениям относительно дискретности во времени, называется синхронной. Асинхронные системы, не удовлетворяющие этим предположениям будут рассмотрены в дальнейшем.

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

Аналогично множество значений выходной переменной у есть выходной алфавит У,

а элемент у называется символом выходного алфавита.

В теории конечных автоматов рассматриваются только конечный входной алфавит Х={х₁,х₂,...,х_n} и конечный выходной алфавит У={у₁,у₂,...у_m}

Результат преобразования входной последовательности символов в выходную, в общем случае, зависит от того, что происходило раньше, т.е. от истории преобразования. Таких предисторий может быть бесконечное множество. Отсюда следует, что система должна иметь бесконечнную память, чтобы помнить все преистории. Введем на множестве предисторий отношение эквивалентности. Две предистории являются эквивалентными, если они одинаковым образом влияют на преобразование входных последовательностей. Следовательно, система достаточно запомнить класс эквивалентности, к которому принадлежит данная история.

В теории конечных автоматов рассматриваются только системы с конечным числом предисторий, иначе говоря с конечным числом состояний, а, следовательно, с конечным объемом памяти.

Теперь можно дать определение класса систем, который называют конечными автоматами.

Определение. Конечным автоматом А называется дискретный преобразователь информации с конечным входным алфавитом Х= {х₁, х₂,...,х_n}, с конечным выходным алфавитом У= {у₁, у₂,...,у_m}, c конечным выходным алфавитом У= {у₁, у₂,...,у_m}, с конечным множеством состояний S={s₁, s₂, …, s_к}, работа которого описывается двумя характеристическими функция:

F_s: S * X S – функция переходов;

F_у : S * X У – функция переходов;

Эти функции можно записать в другом виде:

S(t+1)= F_s [X (+), S(+)];

У(t) = F_у [X (+), S(+)], где Х(t),У(t), S(t) – соответственно входной, выходной символы и внутреннее состояние автомата в момент времени t. Данная система функций может рассматриваться как аналитическая функциональная модель синхронного автомата, известна под названием модели или автомата Мили.

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

S(t+1)= F_s [X (t), S(t)]

У(t) = F_у [ S(t)]

Как видно из выходной функции автомата Мура, выходной символ однозначно определяется состоянием автомата. Другими словами, выходной символ в момент времени + с состоянием автомата в тот же момент времени.

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

У(t) = F_у [ S(t)]

т.е. выходной символ зависит только от комбинации символов, поданных на его вход. Такие автоматы называются примитивными, тривиальными, автоматами без памяти или комбинационными схемами.

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

Способы задания конечных автоматов.

 

Рассмотрим способы задания конечных автоматов на примере автомата Мили.

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

Задание автоматов с помощья таблиц. Характеристические функции F_y и F_s можно задавать с помощью таблицы выходов описывающей функцию выходов Y(t)=F_y[X(t),S(t)] и таблицы переходов, описывающей функцию переходов S(t+1)=F_s[X(t),S(t)].

В таблице переходов, верхней строке соответствуют состояния автомата S_i(t) (i=1,k), а крайний левый столбец отводится для входного символа X_j (j=1,n). На пересечении i-ой строки и j-ого столбца ставится состояние автомата в которое он перейдет в момент времени (t+1).

Таблица выходов организовывается также, но на пересечении i-ой строки и j-ого столбца ставится соответствующий выходной символ Y_l (l=1,m).

Пример. Автомат определен на множествах X={x₁,x₂}, Y={y₁,y₂,y₃}, S={s₀,s₁,s₂,s₃} и описывается таблицами переходов переходов (табл.3.1) и выходов (табл.3.2).

 

 

xj	si(t)		xj	si(t)
s0(t)	s1(t)	s2(t)	s3(t)		s0(t)	s1(t)	s2(t)	s3(t)
x1	s1(t+1)	s2(t+1)	s3(t+1)	s3(t+1)		x1	y2	y2	y1	y2
x2	s0(t+1)	s0(t+1)	s2(t+1)	s1(t+1)		x2	y2	y3	y1	y3

Табл. 3.1.

Табл. 3.2.

Как правило, в таблицах временные параметры не ставятся.

Таблицы переходов и выходов часто объединяют в общую таблицу (табл. 3.3).

 

 

xj	si
s0	s1	s2	s3
x1	s1 y2	s2 y2	s3 y1	s3 y2
x2	s0 y2	s0 y3	s2 y1	s1 y3

Табл. 3.3.

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

Задание автоматов с помощью графов. Одни из наиболее наглядных способов в задания конечных автоматов основан на использовании ориентированных графов. Граф автомата А с k состояниями состоит из k вершин, причем каждая вершина соответствует одному состоянию автомата и обозначается символом этого состояния. Вершины графа могут соединяться друг с другом ориентированными дугами, указывающими направления перехода из одного состояния в другое, которое проводится и обозначается по следующему правилу. Если x_j – такой входной символ, при воздействии которого автомат, находившийся в состоянии S_i, переходит в состояние S_a, и при этом вырабатывает некоторый выходной символ y_l, то образуем пару (x_j,y_l). Тогда множеству входных символов соответствует множество пар (x_j,y_m). Если множество таких пар не пусто, то вершины S_j и S_a соединяются ребром (рис.3.2) и построенное ребро отмечается дизъюнкцией пар (x_j,y_l). В случае, если i=a, ребро начинается и заканчивается в той же вершине S_i (образуя ребро, называемое петлей).

Пример. Автомат заданный на множестве X={x₁,x₂,x₃,x₄,x₅}, Y={y₁,y₂,y₃}, S={s₀,s₁,s₂,s₃,s₄} совмещенной таблицей переходов и выходов (табл.3.4).

 

 

S X	s0	s1	s2	s3	s4
x1	s1 y1	s1 y3	s1 y2	s4 y2	s4 y3
x2	s1 y2	s1 y1	s3 y3	s3 y1	s3 y3
x3	s2 y3	s1 y2	s1 y1	s3 y3	s3 y2
x4	s0 y2	s0 y1	s0 y3	s0 y2	s0 y1
x5	s1 y3	s1 y1	s1 y2	s3 y3	s3 y2

Табл. 3.4.

 

На рис. 3.2. представлен граф автомата, заданного совмещённой таблицей 3.4.

 

Рис 3.2. Граф автомата, заданного табл. 3.4.

 

Отметим, что состояние автомата, вершина графа которого не имеет заходящих дуг, но имеет хотябы одну исходящую, называется переходящим. Из такого состояния можно перейти в какое-то другое, но перейти в это состояние нельзя ни из какого другого состояния.

Тупиковым состоянием называется состояние автомата, соответствующая вершина графа которого не содержит исходящих дуг, но имеет хотя бы одну заходящую. После перехода в это состояние из него нельзя перейти ни в какое другое состояние.

Изолированным состоянием автомата называется состояние, соответствующая вершина графа которого не содержит ни исходящих ни заходящих дуг, а может быть, содержит петли. Из такого состояния нельзя перейти ни в какое другое и в это состояние нельзя перейти ни из какого другого.

Пример. На рис. 3.3. изображен граф переходов автомата, имеющего шесть состояний.

Рис 3.3. Граф переходов автомата с шестью состояниями.

 

Для автомата, представленного на рис.3.3, состояния s₀ и s₄ – переходящие, состояния s₁ и s₃ – тупиковые, а состояние s₅ – изолированное.

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

Автономная матрица. Матрица переходов является математической копией графа переходов. Так как матрица переходов является математической моделью графа переходов, то это позволяет формализовать выполнение некоторых операций над автоматами. Следует отметить, что такое свойство матрицы позволяет выполнять операции тогда, когда граф переходов настолько сложен, что использование визуальных методик исследования автомата становится невозможным.

Для автомата А, имеющего n состояний, матрица переходов имеет размерность nxn и обозначается как [A].

Обозначение i-ого состояния S_i приписывается соответственно i-му столбцу и i-ой строке матрицы.

Пусть S={S₀, S₁, …, S_k} – множество состояний автомата А и пусть b_ij – дуга графа переходов направленная из вершины S_i в вершину S_j. В матрицу ставится дизъюнкция пар, которой отмечено это ребро графа. Если на графе отсутствует ребро, указывающее переход из состояния S_i в состояние S_j, то в соответствующем месте таблицы ставится символ пустого множества Ø.

Пример. Автомат задан совмещенной таблицей переходов (табл. 3.4) и графом переходов (рис. 3.2). Построить матрицу переходов заданного автомата (табл. 3.5).

Si	S0	S1	S2	S3	S4
S0	(x4,y2)	(x1,y1)V(x2,y2)V(x5,y3)	(x3,y3)	Ø	Ø
S1	(x4,y1)	(x3,y3)V(x2,y1)V(x3,y2)V(x5,y1)	Ø	Ø	Ø
S2	(x4,y1)	(x2,y2)V(x3,y1)V(x5,y2)	Ø	(x2,y3)	Ø
S3	(x4,y2)	Ø	Ø	(x2,y1)V(x3,y3)V(x5,y3)	(x1,y2)
S4	(x1,y3)	Ø	Ø	(x2,y3)V(x3,y2)V(x5,y2)	(x1,y3)

Табл. 3.5

Изолированные и эквивалентные автоматы.

Если автомат задан конечным входным алфавитом X={x₁,x₂,…,x_n}, конечным выходным алфавитом Y={y₁,y₂,…, y_m}, имеющий конечное число состояний S={s₁,s₂,…,s_k}, то матрица переходов может быть заполнена K^kn способами, а матрица выходов – m^nk способами. Следовательно, общее число автоматов с заданными алфавитами и заданным числом состояний в точности равно (km)^nk. Если при этом определены функции выходов и переходов, то становится понятно, что при большом числе возможных вариантов заполнения таблицы переходов и выходов, возможны случаи когда автомат А₁ будет отличаться от автомата А₂ только возможными отличаями в обозначениях выходов и состояний.

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

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

Введем обозначение А_1s для обозначение того, что автомат А находится в состоянии S.

Говорят, что состояние S_i автомата А₁ и исостояние S_j автомата А₂ эквивалентны, если при подаче на их входы любой входной последовательности алфавитов формируются одинаковые выходные последовательности символов.

Иначе говоря, эквивалентными называются два состояния автомата, которые нельзя различить никакими входными экспериментами.

Эквивалентность состояний S_i и S_j обозначается равентвом S_i=S_j, а различимость – неравенством S_i≠S_j.

Исходя из определения эквивалентности, можно показать, что эквивалентность состояний обладает свойством рефлективности (S_i=S_j), свойством симметричности (если S_i=S_j, то S_j=S_i) и свойством транзитивности (если S_iRS_j и S_jRS_k, то S_iRS_k, где R – некоторое отношение). Следовательно, эквивалентность состояний можно рассмотривать как обычное отношение эквивалентности, применимое к множествам состояний мощности.

Различимость состояний не обладает свойствами рефлексивности и транзитивности, а следовательно, понятие различимости может относится к парам состояний.

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

Приведем некоторые случаи:

1. Если строки S_i и S_j в таблицах выходов автомата А различаются, то S_i≠S_j.

2. Если строки S_i и S_j в таблицах переходов и выходов автомата А совпадают, то S_i=S_j.

3. Если строки S_i и S_j в таблицах выходов и переходов автомата А становятся одинаковыми при замене каждого обозначения S_i на S_j (или наоборот), то S_i=S_j. В этом случае при приложении любого входного сигнала к A|S_i и к A|S_j выходные символы будут одинаковыми в двух случаях: либо A|S_i и A|S_j переходят в одно и то же состояние, либо в состояние S_i=S_j.

Пары строк, обладающие свойством, приведенным в случае 1, называются явно различимыми, а состояния, стоящие в основном столбце в этих строках – явно различимыми состояниями. Пары строк, обладающие свойствами, приведенными в случаях 2 и 3, называются явно эквивалентными, а состояния, стоящие в основном столбце в этих строках – явно эквивалентными состояниями.

Состояние S_i автомата А₁ и состояние S_j автомата А₂ называются К-эквивалентными, если при подаче на вход автоматов A|S_i и A|S_j входной последовательности символов длины К они вырабатывают одинаковые выходные последовательностисимволов.

Если S_i и S_j не являются К-эквивалентными, то они являются К-различимыми.

К-эквивалентные состояния обладают свойствами рефлексивности, симметричности и транзитивности.

Если два состояния являются К-эквивалентными, то они являются и L-эквивалентными для всех L≤K. Если два состояния являются К-различимыми, то они являются и L-различимыми для всех L≥K.