Виталий Сигорский: Математический аппарат инженера

где p i, q i, r i - количество символов в алфавитах входной переменной x i , выходной переменной y i и переменной состояния s i . При двоичном структурном алфавите р = 2 n , q = 2 m и r = 2 k . Если желают подчеркнуть мощности множеств X , Y и S , на которых определен конечный автомат, то его называют (р, q, r )-автоматом.

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

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

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

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

4. Представления конечных автоматов.Автомат может быть задан различными способами, например, путем словесного описания его функционирования или перечислением элементов множеств X , Y , S , с указанием отношений между ними. При анализе и синтезе конечных автоматов используются стандартные формы представления: таблицы, графы и матрицы. Элементы множеств X , Y , S удобно пронумеровать порядковыми числами, начиная с нуля, например: Х = {0, 1, 2, 3}, Y = {0, 1} и S = {0, 1, 2, 3}. Тогда характеристические функции δ и λ можно представить двумя

- 567 -

таблицами, строки которых соответствуют состояниям, а столбцы - входам. Первая таблица, называемая таблицей переходов, соответствует функции s( ν + 1) = δ (x( ν ), s( ν )), и ее клетки заполняются номерами состояний s( ν + 1), в которые переходит автомат при

воздействии х ( ν ) , и состоянию s( ν ) в данный тактовый момент. Вторая таблица, называемая таблицей выходов, соответствует функции у ( ν ) = λ (x( ν ), s( ν )), и ее клетки заполняются номерами выходов y ( ν ) в данный тактовый момент, которые соответствуют воздействию x( ν ) и состоянию s( ν ) в тот же момент. Например, для заданных множеств X , Y, S такие таблицы могут иметь вид:

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

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

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