Основные определения

Пусть X_i – алфавит входной переменной x_i , а Y_i – алфавит выходной переменной y_i . Конечный автомат с n входамии т выходами характеризуется входным алфавитом X = X₁ X₂ … X_n и выходным алфавитом Y = Y₁ Y₂ … Y_m, причем символами входного алфавита служат слова х = (х₁, х₂, ..., х_n ) длины n, а символами выходного алфавита – слова у = (у₁, у₂, ..., у_m ) длины т, где x_i X_i и y_i Y_i. Особого внимания заслуживают конечные автоматы с двузначным структурным алфавитом, зависимости между входными и выходными переменными которых выражаются булевыми функциями. Их значение обусловлено тем, что любая информация может быть представлена в двоичных кодах (двоично-десятичные коды чисел, телетайпный код в технике связи и т. п.). В то же время при технической реализации автоматов используются преимущественно двоичные элементы и двузначная логика.

В реальных условиях сигналы представляются непрерывными функциями времени, поэтому для надежного различения сигналов требуется, чтобы новые значения на входах появлялись после окончания переходных процессов, связанных с предыдущими значениями. При рассмотрении логической структуры автоматов обычно отвлекаются от существа этих процессов и считают, что переменные изменяются не непрерывно, а мгновенно в некоторые моменты времени, называемые тактами. Интервалы между тактами могут быть различными, но без потери общности их можно считать равными Dt. Предполагается, что тактовые моменты t_n₊₁ = t_n+ Dt определяются синхронизирующими сигналами. Таким образом, вводится понятие дискретного автоматного времени t_n (n = 1, 2, ...), причем переменные зависят не от физического времени, а от номера такта n, т. е. вместо непрерывных функций х(t) рассматриваются дискретные значения х(n).

Кроме входных и выходных переменных, можно выделить некоторую совокупность промежуточных переменных, которые связаны с внутренней структурой автомата. В комбинационных схемах промежуточные переменные непосредственно не участвуют в соотношениях вход – выход. Напротив, выходные функции последовательностных схем в качестве своих аргументов, кроме входных переменных, обязательно содержат некоторую совокупность промежуточных переменных s₁, s₂, ..., s_k, характеризующих состояние схемы. Набор всех возможных состояний, которые присущи данной схеме, называется множеством состояний. Если S₁, S₂, ..., S_k – конечные алфавиты переменных состояния s₁, s₂, ..., s_k, то множество S = S₁ S₂ ... S_k также является конечным множеством.

Строгое определение понятия состояния связывается с той ролью, которую оно играет при описании конечных автоматов. Во-первых, значения совокупности выходных переменных на n-м такте у(n) = (у₁(n), у₂(n), ..., у_m(n)) однозначно определяется значениями входных переменных x(n) = (x₁(n), x₂(n), ..., x_n(n)) и состоянием s(n) = (s₁ (n), s₂(n), ..., s_k(n)) на том же такте, т.е. у(n)= l( x(n),s(n)). Во-вторых, состояние s(n+1) в следующем (n+ 1)-м такте однозначно определяется входными переменными х(n) и состоянием s(n) в предыдущем такте, т. е. s(n+1) = d( x(n),s(n)).

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

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

Рис. 1

Рассмотрим типы конечных автоматов. В технике с понятием автомата обычно связывается некоторое устройство, способное выполнять определенные функции без вмешательства человека или с его ограниченным участием. Однако такое понимание является слишком узким. В широком смысле конечный автомат – это математическая модель, отображающая физические или абстрактные явления самой разнообразной природы. Такая модель успешно используется как в технике (проектирование электронных вычислительных машин, систем управления и связи), так и в других областях – программировании, психологии и физиологии (исследование деятельности нервной системы человека и простейших видов поведения животных), лингвистике (анализ синтаксиса русского, английского или других языков, расшифровка древних рукописей), теории и практике административного управления и т. п. Универсальность теории автоматов позволяет рассматривать с единой точки зрения различные объекты, устанавливать связи и аналогии между ними, переносить результаты из одной области в другую.

Конечный автомат М определяется как система с конечным входным алфавитом X = {x₁, x₂, ..., x_p}, конечным выходным алфавитом Y {v₁, v₂, ..., v_q}, конечным множеством состояний S= {s₁, s₂, ..., s_r}и двумя характеристическими функциями:

s(n+1) = d( x(n),s(n));

у(n)= l( x(n),s(n)),

называемыми соответственно функцией переходов и функцией выходов. Общая блок-схема конечного автомата (рис. 1) может быть представлена в виде комбинационной схемы, реализующей характеристические функции d и l, и памяти, сохраняющей на один такт предыдущее состояние автомата.

В определении автомата участвует три конечных множества X, Y, S и две функции d и l, задающие некоторые отношения между элементами этих множеств. Следовательно, конечный автомат можно обозначить упорядоченной пятеркой М = (X, Y, S, d, l). Мощности множеств X, Y, S равны соответственно:

p= ; q= ; r= ,

где р_i , q_i и r_i – количество символов в алфавитах входной переменной х_i , выходной переменной у_i и переменной состояния s_i. При двоичном структурном алфавите р = 2ⁿ , q = 2^m и s = 2^k. Если желают подчеркнуть мощности множеств X, Y и S, на которых определен конечный автомат, то его называют (р,q,r)-автоматом.

Характеристические функции d и l можно рассматривать как некоторые отображения множества X S или его подмножества D X S соответственно на множества S и Y. Если d: X S S и l: X S Y, автомат называется полным; если только d: X S S, автомат называют полным по переходам. В случае, когда функции d и l определены не для всех наборов из множества X S, автомат называют неполным или частично определенным.

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

Между автоматами этих двух типов имеется взаимная связь и один из них может быть преобразован в другой. Положив в характеристических функциях автомата Мили s^'(n) = ( x(n),s(n)), получим y^'(n) = l ^‘(s^'(n)) и s^'(n+1) = ( x(n+1), s(n+1))=( x(n+1); d( x(n),s(n)))=d^’(x(n+1), s^'(n)), т. е. приходим к автомату Мура. Обратный переход осуществляется подстановкой s(n) =s(n-1), в результате чего получаем y(n) = l^‘(s^'(n))=l^‘(d^’(x(n), s^'(n-1)))= l(x(n), s(n)), а также ), s(n+1))= s^'(n)=d^’(x(n), s^'(n-1))= d^’(x(n), s(n)).

Для комбинационных схем функция перехода не имеет смысла, а функция выходов вырождается к виду y(n) = l((n)). Их называют автоматами без памяти или тривиальными автоматами.

Автомат может быть задан различными способами, например, путем словесного описания его функционирования или перечислением элементов множеств X, Y, S, с указанием отношений между ними. При анализе и синтезе конечных автоматов используются стандартные формы представления: таблицы, графы и матрицы. Элементы множеств X, Y, S удобно пронумеровать порядковыми числами, начиная с нуля, например: X = {0, 1, 2, 3}, Y = {0, 1} и S = {0, 1, 2, 3}. Тогда характеристические функции d и lможно представить двумя таблицами, строки которых соответствуют состояниям, а столбцы – входам. Первая таблица, называемая таблицей переходов, соответствует ), s(n+1)= d(x(n), s(n)), и ее клетки заполняются номерами состояний s(n+1), в которые переходит автомат при воздействии x(n), и состоянии s(n) в данный тактовый момент. Вторая таблица, называемая таблицей выходов, соответствует функции y(n) = l(x(n), s(n)), и ее клетки заполняются номерами выходов y(n) в данный тактовый момент, которые соответствуют воздействию x(n) и состоянию s(n) в тот же момент. Например, для заданных множеств X, Y, S такие таблицы могут иметь следующий вид.

Таблица 1 Таблица 2

s(n+1)= d(x(n), s(n))	y(n) = l(x(n), s(n))
x(n) s(n)		x(n) s(n)

Обе таблицы можно объединить в общую таблицу переходов, если условиться записывать в клетках пары чисел (номер следующего состояния в числителе и номер выхода в знаменателе).

Таблица 3

x(n) s(n)
	3/0	2/0	1/0	3/0
	3/1	2/0	1/0	3/1
	3/1	2/0	2/1	3/1
	3/0	0/0	0/1	1/1

Граф автомата строится таким образом, что его вершины соответствуют состояниям, а направленные дуги обозначаются как дизъюнкции входов, под воздействием которых совершается пере- ход из одного состояния в другое по направлению дуги. В знаменателях записываются номера выходов, соответствующие этим переходам.

Рис. 2

На рис. 2 показан граф, построенный в соответствии с приведенной общей таблицей переходов. Так как из состояния 0автомат переходит в состояния 1, 2 и 3, то из вершины 0 графа исходят дуги в вершины 1, 2 и 3. При этом переход в состояние 1 совершается под воздействием 2 и ему соответствует выход 0, поэтому дуга из вершины 0 в 1 помечается как 2/0. Переход в состояние 2 совершается под воздействием 1 и ему соответствует выход 0, поэтому дуга из вершины 0 в 2 помечается как 1/0. Переходы в состояние 3 совершаются под воздействиями 0 и 3 и им обоим соответствует выход 0, поэтому дуга из вершины 0 в 3 помечается как дизъюнкция 0/0 3/0. Аналогично определяются и другие дуги графа. Петли соответствуют переходам, при которых состояния не изменяются. Так, рассматриваемый автомат переходит из состояния 2 в 2 под воздействиями 1 и 2, которым соответствуют выходы 0 и 1. Следовательно, петля при вершине 2 помечается как дизъюнкция 1/0 2/1.

Матрица соединения автомата М (или матрица переходов) представляет собой квадратную таблицу, в которой номера строк и столбцов соответствуют номерам состояний. Клетка матрицы на пересечении i-й строки и j-го столбца заполняется дизъюнкцией пар «вход – выход», которая приписана дуге графа исходящей из i-й в j-ю вершину. При отсутствии такой ветви клетка заполняется нулем или остается свободной. Так, для рассматриваемого примера имеем следующую матрицу переходов (табл. 4)

Таблица 4