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

Основные определения, виды автоматов

Автоматом (автоматом Мили) называется система из пяти объектов А = (X, S, У, h, J), где X, S, Y — непустые множества; h и f — функции: h: S x X —" S; /: S x X —> Y. Множества X, 5, К называются соответственно входным, внутренним и выходным алфавитами, а их элементы — входными символами, состояниями и выходными символами. Множество 5 называют также множеством состояний автомата А. Функции h и / называются соответственно функцией переходов и функцией выходов автомата. Автомат А называют конечным, если множества Х_} S, Y конечны.

Автомат функционирует в дискретные моменты времени (такты). В t-м такте автомат в состоянии s_teS получает входной символ x_t е X, выдает выходной символ y_t е Y и переходит в состояние s,₊₁ е 5, t = 1, 2,… Закон функционирования автомата во времени задают равенства.

В соответствии с (9.1) и (9.2) автомат А преобразует входное слово х = {x_Xl…, x_t) в выходное слово у = (г/_1?…, у_г) той же длины t_} проходя последовательность внутренних состояний J = (s_{, …, s_f+1), при этом входное слово х переводит состояние s_{ в состояние s_t+{. Состояние называется начальным, состояние s_r+1 — конечным, или финальным.

Множество всех входных (выходных) слов в алфавите X (в алфавите У) обозначим через X* (через F*). Пустое слово обозначим Л. Связанные с функционированием автомата А отображения /г*: S х X*—>5 и f*: S х X* —" У* зададим при каждом 5 е равенствами.

кроме того, для всех х е X, w е X*

Из (9.3) и (9.4) выводится методом математической индукции, что реакция автомата Мили на последовательное введение входных слов v и w равна его реакции на входное слово vw.

Теорема 9.1. Для любых слов v, w е X* и любого s е S автомата Мили верны равенства.

Преобразование h_x множества S, определяемое как подфункция функции h (sу х), соответствующая фиксированному значению х, называется частичной функцией переходов автомата А. При входном слове w = (x_v …, x_t) преобразование h_w множества S есть композиция.

Определим некоторые классы автоматов.

Автомат Л называется регулярным (перестановочным, подстановочным), если все его частичные функции переходов являются подстановками множества S. Полугруппой автомата (группой регулярного автомата) А называется полугруппа (группа) G_A = (h_x(s): х е X). Полугруппа G_A состоит из всех непустых слов в алфавите {h_x(s): х е X). Например, полугруппу (группу) неавтономного регистра сдвига длины п можно рассматривать как полугруппу (группу) автомата Мили А, в котором S = X" и функция переходов h (s_y х) есть отображение неавтономного регистра сдвига.

Функция f_x: S^>Y, определяемая как подфункция функции/(5, х)_у соответствующая фиксированному значению х₉ называется частичной функцией выходов автомата А.

Функцию f_t: Sх X¹ —" Y, отображающую множество начальных состояний и входных слов длины t во множество значений t-го знака выходного слова, назовем t-й выходной функцией автомата A, t= 1,2, т. е. y_t = f_t(s, x (t)) =

= A^hx (t-1)00. X_t) = f_X'(h_W-p)) —

Автомат А внутренне автономный, если функция переходов h (s_y х) не зависит от х, т. е. h: S —> S. Выходные функции внутренне автономного автомата задана выражением.

где h°(s) = s при любом s е 5, t = 1, 2,…

Автомат А называется автоматом Мура или внешне автономным, если функция выходов f (Sy х) не зависит от х, т. е. /: S —> У. Выходные функции автомата Мура имеют вид.

т, e. f_t(s, x (t)) зависит от x_t несущественно, t- 1,2,…

Внутренне и внешне автономный автомат А = (S, У, /г, У) называют автономным. Выходные функции автономного автомата зависят только от начального состояния s: f_t(s) = /(A^M(s)).

Внутренне автономный автомат Л с тождественной функцией переходов (обозначение Л = (А, 5, У, /)) назовем автоматом с постоянной памятью (а.п.п.). Выходные функции а.п.п. заданы выражением.

Автомат А = (X, У, f) реализует функцию f:X—> Y и называется автоматом без памяти или комбинационной схемой, если его функционирование определено лишь функцией выходов.

Автомат А = (X, 5, Л) называют автоматом без выходов, если функционирование автомата определяется лишь функцией переходов. Автономный автомат без выходов А = (S, h) есть преобразование h множества S.

Если начальное состояние s е S автомата Мили А фиксировано, то пара (А, {л*}) называется инициальным автоматом (им.), обозначим A_s = (А, {л}).