Рис. 235. Блок-схема конечного автомата.
Конечный автомат М определяется как система с конечным входным алфавитом Х = { ξ1, ξ2, ... , ξp}, конечным выходным алфавитом Y = {v1, v2, …, vq}, конечным множеством состояний S = {σ1, σ2, ..., σi}, и двумя характеристическими функциями:
s(ν + 1) = δ (x(ν), s(ν));
у(ν) = λ (х(ν), s(ν)),
называемыми соответственно функцией переходов и функцией выходов. Общая блок-схема конечного автомата (рис. 235) может быть представлена в виде комбинационной схемы, реализующей характеристические функции δ и λ, и памяти, сохраняющей на один такт предыдущее состояние автомата.
В определении автомата участвует три конечных множества X, Y, S и две функции δ и λ, задающие некоторые отношения между
- 566 -
элементами этих множеств. Следовательно, конечный автомат можно обозначить упорядоченной пятеркой М = (X, Y, S, δ, λ). Мощности множеств X, Y, S равны соответственно:
где pi, qi, ri - количество символов в алфавитах входной переменной xi, выходной переменной yi и переменной состояния si. При двоичном структурном алфавите р = 2n, q = 2m и r = 2k. Если желают подчеркнуть мощности множеств 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}. Тогда характеристические функции δ и λ можно представить двумя