АБСТРА́КТНЫЙ АВТОМА́Т

АБСТРА́КТНЫЙ АВТОМА́Т, математическая модель дискретного управляющего устройства. На практике часто возникает необходимость моделировать поведение объектов, выходные сигналы которых зависят не только от входных сигналов в данный момент времени, но и от ранее поступавших входных сигналов, которые изменяли состояние объекта, т. е. от его предыстории. В абстрактном автомате понятие внутреннего состояния позволяет неявно (без введения времени) учесть поведение моделируемого объекта (процесса, системы) в предыдущие моменты времени, которое отражается во внутреннем состоянии автомата. В классической модели абстрактного автомата выходные сигналы возникают после поступления входных сигналов и изменения внутреннего состояния. Абстрактный автомат задаётся кортежем из 5 или 6 элементов: $A \Leftrightarrow \left\langle {X, Y,G, f (x, g),\phi (x, g), {g_0}} \right\rangle \, $, где $X$ – множество входных сигналов (входной алфавит автомата); $Y$ – множество выходных сигналов (выходной алфавит автомата); $G = \left\{ {{g_0}, {g_1},… {g_k}} \right\}$ – множество внутренних состояний (алфавит состояний автомата); $f (x, g)$ – функция переходов, реализующая отображение $X \times G \to G; \, \phi (x, g)$ – функция выходов, реализующая отображение $X \times G \to Y; \, g_0 \in G$ – начальное состояние автомата (иногда специально не выделяется). Если ввести дискретные такты (фактически моменты времени) $t = \,\,\, 0,\,\, 1,\,\, 2,\,\, 3,…$, то в некоторый такт $t=i$ выходной сигнал $y (i) \in Y$ и внутреннее состояние $g (i) \in G$ полностью определяются его начальным внутренним состоянием $g (0)\in G$ и входным сигналом $x (0)\in X$.

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

Абстрактный автомат можно задать (описать) графом или таблицей переходов. Граф переходов (диаграмма состояний) – графическое представление множества состояний и функции переходов; является размеченным ориентированным графом, вершины которого – состояния автомата, дуги – переходы из одного состояния в другое, метки дуг – символы входных сигналов, по которым происходят переходы из одного состояния в другое. Если переход из состояния $g_i (t)$ в $g_i (t+1)$ происходит под действием разных входных сигналов, то они записываются над соответствующей дугой. Таблица переходов – табличное представление функции переходов $g (t + 1) = f[x (t), g (t)],\,\,\,\, t = \,\,\, 0,\,\, 1,\,\, 2,\,\, 3,…{\rm{ }}$. В каждой строке таблицы указывается одно состояние, а столбцу соответствует один входной символ. На пересечении строки и столбца записывается состояние, в которое должен перейти автомат, а также вырабатываемый выходной сигнал. В дискретном автомате некоторое множество входных слов (последовательностей, содержащих символы входного алфавита автомата) отображается в выходные слова (последовательности, содержащие символы выходного алфавита). Если на вход автомата, установленного в начальное состояние, подавать последовательно символы входного слова, то на выходе автомата последовательно появятся символы выходного слова.

Абстрактные автоматы классифицируют на: конечные (для них множества $X, Y, G$ являются конечными); полностью определённые (области определения функций переходов и выходов совпадают с декартовым произведением множеств $X \times G$; в частично определённых автоматах это не выполняется); синхронные автоматы (изменяют состояния и вырабатывают выходные сигналы в дискретные такты); асинхронные автоматы (вырабатывают выходные сигналы только после попадания в состояния из некоторого подмножества состояний); детерминированные и недетерминированные (выделяют вероятностные и стохастические). В недетерминированном автомате предыдущее состояние и сигнал на входе ещё не определяют полностью последующего его состояния, а только обусловливают класс возможных состояний, т. е. в автомате переход в следующее состояние происходит случайным образом, отражает факт невозможности учесть весь спектр внешних воздействий для некоторых объектов. Стохастический автомат – обобщение детерминированного автомата, у которого вместо функций переходов и выходов в общем случае задаются распределения вероятностей дискретного типа, т. е. предыдущее состояние и сигнал на входе определяют классы возможных состояний и выходных сигналов, а конкретные состояния и выходные сигналы появляются с некоторой вероятностью, причём суммы вероятностей состояний и выходных сигналов из одного класса равны единице, что отражает факт обязательного перехода в новое состояние из класса и выработки выходного сигнала из соответствующего класса. Вероятностный автомат – обобщение детерминированного автомата, в котором переход под воздействием входного сигнала из одного состояния в другое происходит с заданной вероятностью, а вероятность перехода зависит от последовательностей предыдущих состояний и входных сигналов. Вероятностные автоматы используют для моделирования сложных процессов, например дистанционного автоматического управления движением объектов в пространстве.

К конечным синхронным автоматам (наиболее распространённый класс абстрактных автоматов) относятся автоматы Мили и Мура. Функционирование автомата Мили задаётся уравнениями

$$y (t + 1) = \phi [x (t), g (t)]; \,\,\,\,\,\,\, g (t + 1) = f[x (t), g (t)],\,\,\,\, t = 0,\,\, 1,\,\, 2,\,\, 3,…$$ Функционирование автомата Мура задаётся уравнениями $$y (t + 1) = \phi [g (t)]; \,\,\,\, g (t + 1) = f[x (t), g (t)],\,\,\,\, t = \,\, 0,\,\, 1,\,\, 2,\,\, 3,…$$В частном случае функция выходов автомата Мура линейная:$$y (t + 1) = k \cdot g (t) + c; \,\,\,\,\,\, g (t + 1) = f[x (t), g (t)],\,\,\,\, t = \,\,\, 0,\,\, 1,\,\, 2,\,\, 3,… $$что позволяет выделить другие виды автоматов, в частности клеточные автоматы.