Способы задания автоматов Мили

Для задания автомата А = (X, 5, У, h, /) необходимо описать каждое из множеств X, S, Y и задать отображения /г и /. Это делается различными способами.

Зададим алфавиты автомата: X = {^, S = {а_{у

…, о"}; У = {Pj,…, р_;и}. Таблица автомата состоит из двух частей: левая часть задает функцию переходов, правая часть — функцию выходов.

Из данной таблицы следует, что число различных автоматов Мили (различных таблиц) с алфавитами мощности г, /?, т равно (тп)^П1.

Пусть max{r, п, т) = k, тогда функции h и / можно рассматривать как функции Л-значной логики (частично определенные, если min{r, п} < k). Следовательно, можно описать алфавиты X, S, У и задать функции Ли/ формулами или алгоритмами.

Автомат Мили А = (X, 5, У, Л, f) задают автоматным графом (или графом автомата) — орграфом Т_Л = (S, Е) с помеченными вершинами и дугами. Пара (а, а_;) е? найдется ?/€ X, при котором Л (а, ?/) = о,. Дуга (а" а,-) помечена набором символов (^ /р^,…,^ /р_7/), что равносильно выполнению равенств, и = 1,…, t:

Для автомата Мура А в Г_л дуга (а, а_;) помечена набором),.

означающим, что h (a_if^L) = Oj>v= 1,t, а вершина а, — символом Р/, где Р,_;=М);

Автомат, А (и автоматный граф Г_л) называется сильно связным, если из каждого состояния можно перейти в любое другое состояние при некотором входном слове. Автомат А (и автоматный граф Г_л) связен, если связен граф, полученный из Г_л заменой дуг на ребра.

Множество состояний всякого конечного автомата (вершин автоматного графа) разбивается на г компонент связности, 1 < г < |б1.

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

1. Неавтономный регистр сдвига длины п с одной обратной связью ty (x_n,…, Х) (рис. 9.1). Это автомат Мура, в котором Х= Y = {0, 1}, S = V_n, f — б.ф. выходов, h задана системой б.ф.: h (x_w …, х_х, а) = (а © (р (х_п,…, х_{), х_п,…, х₂)', f (x_n, …, x_v а) = х_х. При нулевой входной последовательности автомат равносилен автономному регистру сдвига.

Рис. 9.1. Неавтономный регистр сдвига.

2. Внутренне автономный автомат на основе регистра сдвига (рис. 9.2). Функции переходов и выходов этого автомата имеют вид h (x_n, …, x_v а) = = (ф (*",… *0, х_п, х₂); f (x", x_t, а) = а © х,.

Рис. 9.2. Внутренне автономный автомат на основе регистра сдвига.

Полугруппа автомата А есть циклическая полугруппа (h).