Читать «Математический аппарат инженера» онлайн - страница 63

где p_i, q_i, r_i - количество символов в алфавитах входной переменной x_i, выходной переменной y_i и переменной состояния s_i. При двоичном структурном алфавите р = 2ⁿ, 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 такие таблицы могут иметь вид:

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