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

Конечные автоматы

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

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

При написании данной разработки использованы литературные источники [1-4].

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

В реальных условиях сигналы представляются непрерывными функциями времени, поэтому для надежного различения сигналов требуется, чтобы новые значения на входах появлялись после окончания переходных процессов, связанных с предыдущими значениями. При рассмотрении логической структуры автоматов обычно отвлекаются от существа этих процессов и считают, что переменные изменяются не непрерывно, а мгновенно в некоторые моменты времени, называемые тактами. Интервалы между тактами могут быть различными, но без потери общности их можно считать равными D t. Предполагается, что тактовые моменты t _n+1 = t _n + D t определяются синхронизирующими сигналами. Таким образом, вводится понятие дискретного автоматного времени 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 )).

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

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

Рис. 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 можно рассматривать как некоторые отображения множества XS или его подмножества DXS соответственно на множества S и Y. Если d: XS S и l: XS Y, автомат называется полным; если только d: XS S, автомат называют полным по переходам. В случае, когда функции d и l определены не для всех наборов из множества XS, автомат называют неполным или частично определенным.

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

Между автоматами этих двух типов имеется взаимная связь и один из них может быть преобразован в другой. Положив в характеристических функциях автомата Мили 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

	2/0	1/0	0/03/0
	2/0	1/0	0/13/1
		1/02/1	0/13/1
1/02/1	3/1		0/0