Абстрактный автомат

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

${\displaystyle A\Leftrightarrow \left\langle {X,Y,G,f(x,g),\phi (x,g),{g_{0}}}\right\rangle \,}$,

где ${\displaystyle X}$ – множество входных сигналов (входной алфавит автомата);

${\displaystyle Y}$ – множество выходных сигналов (выходной алфавит автомата);

${\displaystyle G=\left\{{{g_{0}},{g_{1}},\ldots {g_{k}}}\right\}}$ – множество внутренних состояний (алфавит состояний автомата);

${\displaystyle f(x,g)}$ – функция переходов, реализующая отображение ${\displaystyle X\times G\to G}$;

${\displaystyle \phi (x,g)}$ – функция выходов, реализующая отображение ${\displaystyle X\times G\to Y}$;

${\displaystyle g_{0}\in G}$ – начальное состояние автомата (иногда специально не выделяется).

Если ввести дискретные такты (фактически моменты времени) ${\displaystyle t=\,\,0,\,\,1,\,\,2,\,\,3,\ldots }$, то в некоторый такт ${\displaystyle t=i}$ выходной сигнал ${\displaystyle y(i)\in Y}$ и внутреннее состояние ${\displaystyle g(i)\in G}$ полностью определяются его начальным внутренним состоянием ${\displaystyle g(0)\in G}$ и входным сигналом ${\displaystyle x(0)\in X}$.

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

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

Абстрактный автомат можно задать (описать) графом или таблицей переходов.

Граф переходов (диаграмма состояний) – графическое представление множества состояний и функции переходов; является размеченным ориентированным графом, вершины которого – состояния автомата, дуги – переходы из одного состояния в другое, метки дуг – символы входных сигналов, по которым происходят переходы из одного состояния в другое. Если переход из состояния ${\displaystyle g_{i}(t)}$ в ${\displaystyle g_{i}(t+1)}$ происходит под действием разных входных сигналов, то они записываются над соответствующей дугой.

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

Абстрактные автоматы классифицируют на:

• конечные (для них множества ${\displaystyle X,Y,G}$ являются конечными);
• полностью определённые (области определения функций переходов и выходов совпадают с декартовым произведением множеств ${\displaystyle X\times G}$; в частично определённых автоматах это не выполняется);
• синхронные автоматы (изменяют состояния и вырабатывают выходные сигналы в дискретные такты);
• асинхронные автоматы (вырабатывают выходные сигналы только после попадания в состояния из некоторого подмножества состояний);
• детерминированные и недетерминированные (выделяют вероятностные и стохастические).

В недетерминированном автомате предыдущее состояние и сигнал на входе ещё не определяют полностью последующего его состояния, а только обусловливают класс возможных состояний, т. е. в автомате переход в следующее состояние происходит случайным образом, отражает факт невозможности учесть весь спектр внешних воздействий для некоторых объектов.

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

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

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

${\displaystyle y(t+1)=\phi [x(t),g(t)];\,\,\,\,\,\,\,g(t+1)=f[x(t),g(t)],\,\,\,\,t=0,\,\,1,\,\,2,\,\,3,\ldots }$

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

${\displaystyle y(t+1)=\phi [g(t)];\,\,\,\,g(t+1)=f[x(t),g(t)],\,\,\,\,t=\,\,0,\,\,1,\,\,2,\,\,3,\ldots }$

В частном случае функция выходов автомата Мура линейная:

${\displaystyle y(t+1)=k\cdot g(t)+c;\,\,\,\,\,\,g(t+1)=f[x(t),g(t)],\,\,\,\,t=\,\,\,0,\,\,1,\,\,2,\,\,3,\ldots }$,

что позволяет выделить другие виды автоматов, в частности клеточные автоматы.