Понятие конечного автомата

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

Пусть X_i - алфавит входной переменной х_i, а Y_i – алфавит выходной переменной y_i. Конечный автомат с n входами и т выходами характеризуется входным алфавитом Х = Х₁ ´ Х₂ ´... Х_n и выходным алфавитом Y = Y₁ ´ Y₂ ´... Y_m, причем символами входного алфавита служат слова x = (x₁, x₂, …, x_n) длины n, а символами выходного алфавита - слова y = (y₁, y₂, …, y_m) длины т, где x_i Î X_i и y_i Î Y_i. Особого внимания заслуживают конечные автоматы с двузначным структурным алфавитом, зависимости между входными и выходными переменными

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

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

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

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

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

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

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

Конечный автомат М определяется как система с конечным входным алфавитом Х = { }, конечным выходным алфавитом Y = { v ₁, v ₂, …, v _q}, конечным множеством состояний S = { }, и двумя характеристическими функциями:

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

у (n) = (х (n), s (n)),

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

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

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

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

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

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

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

Представления конечных автоматов. Автомат может быть задан различными способами, например, путем словесного описания его функционирования или перечислением элементов множеств X, У, S, с указанием отношений между ними. При анализе и синтезе конечных автоматов используются стандартные формы представления: таблицы, графы и матрицы. Элементы множеств X, У, S удобно пронумеровать порядковыми числами, начиная с нуля, например: Х = {0, 1, 2, 3}, У = {0, 1} и S = {0, 1, 2, 3}. Тогда характеристические функции и можно представить двумя таблицами, строки которых соответствуют состояниям, а столбцы - входам. Первая таблица, называемая таблицей переходов, соответствует функции s (v + 1) = (x (v), s (v)), и ее клетки заполняются номерами состояний s (v + 1), в которые переходит автомат при

=

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

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

На рис. 28 показан граф, построенный в соответствии с приведенной выше общей таблицей переходов. Так как из состояния 0 автомат переходит в состояния 1, 2 и 3, то из вершины О графа исходят дуги в вершины 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 -ю вершину. При отсутствии такой ветви клетка заполняется нулем или остается свободной. Так для рассматриваемого примера имеем:

Date: 2016-02-19; view: 663; Нарушение авторских прав