f – функция переходов автомата;

g – функция выходов автомата;

a⁽⁰⁾ – начальное состояние автомата.

А бстрактный автомат (рис.3.3.) имеет один входной и один выходной канал. В каждый момент дискретного автоматного времени t=0,1,2,… автомат находится в определённом состоянии а(t) из множества А состояний автомата, причём в начальный момент t=0 он находится всегда в начальном состоянии a(t₀)=a⁽⁰⁾. Будем считать, что a⁽⁰⁾=a₁. В момент t, будучи в состоянии a(t)A, автомат способен воспринять на входном канале сигнал x(t)X и выдать на выходном канале сигнал y(t)Y

y(t)=g(a(t),x(t)),

переходя в состояние а(t+1)

а(t+1)=f(a(t), x(t)).

Другими словами, если на вход автомата, установленного в начальное состояние а₁, подавать буква за буквой некоторую последовательность букв входного алфавита – входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита – выходное слово. Таким образом, абстрактный автомат осуществляет словарное преобразование входных слов в выходные.

Автомат называется конечным, если конечные алфавиты A, X, Y. В дальнейшем будем рассматривать только конечные автоматы и термин «конечные» будем опускать. Автомат называется полностью определённым (полный автомат), если функции выходов g и переходов f определены на множестве всех пар вида <a_m,x_j>, где a_mA, x_jX. У частичного автомата функции g и f определены не для всех пар <a_m,x_j>.

На практике наибольшее распространение получили автомат Мили и Мура, которые отличаются способом формирования выходного сигнала g(t).

Закон функционирования автомата Мили задаётся уравнениями

а(t+1)=f(a(t), x(t)); t=0,1,2,…

y(t)=g(a(t), x(t)),

а закон функционирования автомата Мура задаётся уравнениями

а(t+1)=f(a(t), x(t)); t=0,1,2,…

y(t)=g(a(t)).

В автомате Мура выходной сигнал формируется в состоянии a(t), а в автомате Мили на переходе из a(t) в a(t+1).

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

Для любого автомата Мили существует эквивалентный ему автомат Мура, и наоборот. Выходной сигнал автомата Мура задержан на такт относительно выходного сигнала эквивалентного ему автомата Мили.

3.2.2. Методы задания автоматов.

Чтобы задать конечный автомат S, необходимо описать все элементы множества S={X, Y, A, f, g, a⁽⁰⁾}, т.е. входной и выходной алфавиты и алфавит состояний, а такие функции переходов и выходов. Среди множества состояний необходимо выделить начальное состояние а⁽⁰⁾=а₁. Осуществляет несколько способов задания работы автомата, но наиболее часто используются следующие:

1. В виде графа переходов и выходов.

2. В виде таблиц переходов и выходов.

3. В виде матриц переходов и выходов.

Задание автомата в виде графа переходов и выходов.

Г раф автомата – ориентированный связный граф. Вершины соответствуют состояниям автомата, а дуги - переходу из состояния a(t) в состояние a(t+1): a_S=f(a_m, x_j)

Изображения графов для автоматов Мура и Мили имеют отличительные особенности (рис. 3.4. и 3.5). У автомата Мура выходной сигнал записывается внутри вершины или рядом с ней, а у автоматов Мили над дугой: или у её конца, при этом входной сигнал изображается в начале дуги, или под входным сигналом. Тогда входной и выходной сигналы отделяются чертой.

Пример 3.1.

На рис. 3.6. и 3.7. приведены графы эквивалентных автоматов Мура S₁ и Мили S₂, определённых на алфавитах x={x₁,x₂,x₃,x₄} и y={y₁,y₂,y₃}. Эти автоматы на любую входную последовательность, оканчивающуюся на x₁x₂(… x₁x₂), формируют выходной сигнал y₂ (… y₂), а на x₁x₂x₃ (… x₁x₂x₃) сигнал y₃ (… y₃). Говорят, что автоматы распознают последовательности x₁x₂ или x₁x₂x₃. Назовём их правильными. Если входные символы не образуют правильной последовательности или пришли не все символы правильной последовательности формируется выходной сигнал y₁.

Задание автомата в виде таблиц переходов и выходов.

Описание автоматов в виде таблиц демонстрируется рис. 3.8. и 3.9, где изображены таблицы переходов и выходов эквивалентных автоматов Мура S₂ и Мили S₂, графы которых приведены на рис. 3.6 и 3.7.

Строки этих таблиц соответствуют входным сигналам, а столбцы – состояниями, причём крайний левый столбец состояний обозначен начальным состоянием a₁. В таблице переходов внутренняя клетка, находящаяся на пересечении строки и столбца, соответствует состоянию перехода a(t+1).

Для автомата Мили таблица выходов совмещены с таблицей переходов: над чертой в клетке записывается состояние а(t+1), a под ней – выходной сигнал y(t).

Задание автомата в виде матриц переходов и выходов.

Задание автоматов в виде матриц демонстрируется на рис. 3.10 и 3.11, где изображены матрицы рассмотренных выше автоматов S₁ и S₂.

Матрица переходов является квадратной матрицей.

Матрицы переходов и выходов имеют теоретическое значение, и используется при изучении поведения абстрактных автоматов.

Табличная форма представления матриц переходов и выходов.

На практике часто используется табличная форма представления матриц (рис. 3.12 и 3.13)

3.2.3. Минимизация числа внутренних состояний абстрактных автоматов.

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

Эквивалентными называются такие два состояния автомата, замена которых одно на другое не изменяет результатов словарного преобразования на всем множестве допустимых входных слов. Можно говорить как о полной эквивалентности внутренних состояний (для входных слов неограниченной длины), так и о k-эквивалентности состояний (для слов длиной в k символов). В дальнейшем классы эквивалентных и k-эквивалентных внутренних состояний будут соответственно обозначаться как П и П_k .

Процедура минимизации числа внутренних состояний абстрактного автомата состоит из следующих шагов:

1. Находятся последовательные разбиения П₁ , П₂ ,…, П_k алфавита внутренних состояний на классы одно-, двух-, …, k-эквивалентных состояний, до тех пор, пока на каком-то k+1-м шагом не окажется, что П_k+1= П_k . Очевидно, что при достижении этого тождества можно утверждать, что П_k= П , т.е. что k-эквивалентные состояния являются полностью эквивалентными. Нетрудно увидеть, что число шагов этой процедуры не может превысить значения l -1, где l -размеры алфавита внутренних состояний автомата.

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

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

4. В качестве начального состояния автомата выбирается или начальное состояние исходного автомата, или любое ему эквивалентное.

Рассмотрим пример минимизации автомата Мили, заданного совмещенной таблицей переходов и выходов (табл. 3.1.).

Таблица 3.1.

Класс П₁ выделяется из табл. 3.1. путем объединения тех внутренних состояний, которые характеризуются одинаковой реакцией на слова длиной в один символ. Заметим, что в понятие реакции входит только выходной сигнал, поскольку основным назначением автомата является осуществление словарного преобразования. Для класса П₁ выполняются:

П₁ ={ A ₁ ¹, A ₂ ¹}; A ₁ ¹={ a ₁, a ₂, a ₅, a₇, a₈}; A ₂ ¹={ a₃, a₄, a₆, a₉, a₁₀, a₁₁, a₁₂}.

Строим таблицу П₁ (табл. 3.2.), получая ее из совмещенной таблицы заменой символов исходного алфавита внутренних состояний на классы 1-эквивалентности.

Очевидно, что любая пара 1-эквивалентных состояний будет и 2-эквивалентна, если они любым входным сигналом будут переводиться в 1-эквивалентные. Практически это означает, что 2-эквивалентными будут те состояния, которые уже входя в тот или иной класс эквивалентности, в данной таблице имеют одинаковые столбцы. Тогда по табл. 3.2. для класса П₂ получаем: П₂ ={ A ₁ ², A ₂ ², A ₃ ², A ₄ ²}; A ₁ ²={ a₁, a₂};