Абстрактный автомат
Абстра́ктный автома́т, математическая модель дискретного управляющего устройства. На практике часто возникает необходимость моделировать поведение объектов, выходные сигналы которых зависят не только от входных сигналов в данный момент времени, но и от ранее поступавших входных сигналов, которые изменяли состояние объекта, т. е. от его предыстории. В абстрактном автомате понятие внутреннего состояния позволяет неявно (без введения времени) учесть поведение моделируемого объекта (процесса, системы) в предыдущие моменты времени, которое отражается во внутреннем состоянии автомата. В классической модели абстрактного автомата выходные сигналы возникают после поступления входных сигналов и изменения внутреннего состояния. Абстрактный автомат задаётся кортежем из 5 или 6 элементов:где – множество входных сигналов (входной алфавит автомата);
– множество выходных сигналов (выходной алфавит автомата);
– множество внутренних состояний (алфавит состояний автомата);
– функция переходов, реализующая отображение ;
– функция выходов, реализующая отображение ;
– начальное состояние автомата (иногда специально не выделяется).
Если ввести дискретные такты (фактически моменты времени) то в некоторый такт выходной сигнал и внутреннее состояние полностью определяются его начальным внутренним состоянием и входным сигналом .
Абстрактный автомат, находящийся в начальном состоянии, инициализируется (начинает работу) при появлении входных сигналов. Абстрактный автомат прекращает работу в случаях перехода в некоторое фиксированное состояние или превышения количества тактов работы (времени). Два абстрактных автомата называются эквивалентными, если преобразуют одно множество входных сигналов в идентичные множества выходных сигналов, отличающиеся, возможно, обозначениями символов; при этом они могут иметь разное количество внутренних состояний и выполнять преобразование за разное количество тактов. В теории автоматов формулируются типовые задачи:
синтез автоматов (построение автомата, решающего поставленную задачу отображения множества входных сигналов в выходные);
анализ автоматов (доказательство, что построенный абстрактный автомат из некоторого класса решает поставленную задачу за требуемое количество тактов);
минимизация автоматов (построение автомата, эквивалентного исходному, имеющему меньшее количество внутренних состояний);
структурный синтез автоматов (построение автомата из заданного набора элементов; применяется, например, при синтезе цифровых электронных схем на заданной элементной базе).
Абстрактный автомат можно задать (описать) графом или таблицей переходов.
Граф переходов (диаграмма состояний) – графическое представление множества состояний и функции переходов; является размеченным ориентированным графом, вершины которого – состояния автомата, дуги – переходы из одного состояния в другое, метки дуг – символы входных сигналов, по которым происходят переходы из одного состояния в другое. Если переход из состояния в происходит под действием разных входных сигналов, то они записываются над соответствующей дугой.
Таблица переходов – табличное представление функции переходов . В каждой строке таблицы указывается одно состояние, а столбцу соответствует один входной символ. На пересечении строки и столбца записывается состояние, в которое должен перейти автомат, а также вырабатываемый выходной сигнал. В дискретном автомате некоторое множество входных слов (последовательностей, содержащих символы входного алфавита автомата) отображается в выходные слова (последовательности, содержащие символы выходного алфавита). Если на вход автомата, установленного в начальное состояние, подавать последовательно символы входного слова, то на выходе автомата последовательно появятся символы выходного слова.
Абстрактные автоматы классифицируют на:
конечные (для них множества являются конечными);
полностью определённые (области определения функций переходов и выходов совпадают с декартовым произведением множеств ; в частично определённых автоматах это не выполняется);
синхронные автоматы (изменяют состояния и вырабатывают выходные сигналы в дискретные такты);
асинхронные автоматы (вырабатывают выходные сигналы только после попадания в состояния из некоторого подмножества состояний);
детерминированные и недетерминированные (выделяют вероятностные и стохастические).
В недетерминированном автомате предыдущее состояние и сигнал на входе ещё не определяют полностью последующего его состояния, а только обусловливают класс возможных состояний, т. е. в автомате переход в следующее состояние происходит случайным образом, отражает факт невозможности учесть весь спектр внешних воздействий для некоторых объектов.
Стохастический автомат – обобщение детерминированного автомата, у которого вместо функций переходов и выходов в общем случае задаются распределения вероятностей дискретного типа, т. е. предыдущее состояние и сигнал на входе определяют классы возможных состояний и выходных сигналов, а конкретные состояния и выходные сигналы появляются с некоторой вероятностью, причём суммы вероятностей состояний и выходных сигналов из одного класса равны единице, что отражает факт обязательного перехода в новое состояние из класса и выработки выходного сигнала из соответствующего класса.
Вероятностный автомат – обобщение детерминированного автомата, в котором переход под воздействием входного сигнала из одного состояния в другое происходит с заданной вероятностью, а вероятность перехода зависит от последовательностей предыдущих состояний и входных сигналов. Вероятностные автоматы используют для моделирования сложных процессов, например дистанционного автоматического управления движением объектов в пространстве.
К конечным синхронным автоматам (наиболее распространённый класс абстрактных автоматов) относятся автоматы Мили и Мура. Функционирование автомата Мили задаётся уравнениями
Функционирование автомата Мура задаётся уравнениями В частном случае функция выходов автомата Мура линейная:что позволяет выделить другие виды автоматов, в частности клеточные автоматы.