Абстрактный синтез конечных автоматов — это один из этапов синтеза автоматов, который заключается в формировании абстрактного автомата при помощи одного из методов задания отображения «вход — выход», реализуемого этим автоматом.
Введение
В вычислительной технике применяются следующие классы схем:
- Класс комбинационных схем.
- Класс цифровых автоматов.
Основным отличием комбинационных схем может считаться функциональная зависимость между входными и выходным сигналами:
y(t) = f(x(t)).
При этом, когда отсутствует входной сигнал, то и выходной сигнал также отсутствует, так как подобные схемы не обладают памятью. В отличие от комбинационных схем, схемы цифровых автоматов имеют в своем составе компоненты памяти, то есть запоминающие компоненты. В цифровых автоматах выходные сигналы в какой-либо момент времени определяются не только лишь значениями входных сигналов в тот же самый временной период, но и состоянием схемы, которое, при этом, должно определяться величинами входных сигналов, поступавших в предыдущие моменты времени.
Абстрактный синтез конечных автоматов
Автоматом является дискретный преобразователь информации, который способен принимать разные состояния, переходить под влиянием входных сигналов из одного состояния в другое и формировать разные выходные сигналы. В случае, когда количество всех состояний автомата, как и совокупность множеств входных и выходных сигналов, являются конечными, то автомат именуется конечным автоматом.
Термин «состояние» вводится по той причине, что иногда появляется необходимость описать поведение систем, выходные сигналы которых обладают зависимостью не только от состояния на входах в текущий момент времени, но и от некоторой предыстории, то есть от сигналов, поступивших на входы системы раньше. Состояния могут соответствовать определённой памяти о прошлых событиях, что позволяет убрать временной фактор как явную переменную и отобразить выходные сигналы в виде функции состояния и входов в текущий момент времени.
Информацию, которая поступает на вход автомата, а также информацию на его выходе, обычно кодируют при помощи конечной совокупности символов. Данную совокупность именуют алфавитом, а отдельные символы, которые образуют алфавит, называют буквами. Каждая упорядоченная очерёдность букв является словом в этом алфавите. К примеру, в алфавите:
X = (x1, x2),
который состоит из двух букв, словами будут:
x1, x2, x1x1, x1x2, x2x1, x2x2, x1x1x1 и так далее.
Наряду со словами, которые состоят не меньше чем из одной буквы, существует слово, не имеющее ни одной буквы. Такое слово принято обозначать символом «е» и именовать как пустое слово или пустая буква.
Математической моделью реального комбинационного автомата считается абстрактный автомат, имеющий один входной канал и один выходной канал, как показано на рисунке ниже.
Рисунок 1. Абстрактный автомат. Автор24 — интернет-биржа студенческих работ. Автор24 — интернет-биржа студенческих работ
Автомат может работать в каждый дискретный момент времени, интервал между которыми Т именуется тактом. Причём в эти дискретные моменты времени на вход автомата подаётся одна из букв входного алфавита, после чего автомат должен перейти из одного состояния в другое и на выход будет выдана одна из букв, имеющихся в составе выходного алфавита. В зависимости от того, каким образом реализуется задание длительности такта Т, существуют автоматы синхронного действия (T = const), и асинхронного действия (T≠const). Наиболее часто используются синхронные автоматы, работающие в дискретные моменты времени, которые принято обозначать целыми неотрицательными натуральными числами t = 0, 1, 2, 3, … , воспринимаемыми как номера тактов.
Чтобы задать любой комбинационный автомат S, следует задать совокупность из пяти объектов, то есть S {A, X, Y, d, l}, где:
- A = {a0, a1, a2, ..., am, ..., aM} является множеством состояний автомата.
- X = {x1, x2, …, xf ,…, xF} является множеством входных сигналов или входным алфавитом.
- Y = {y1, y2, …, yg,…, yG} является множеством выходных сигналов или выходным алфавитом.
- d является функцией переходов, определяющей состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, то есть a(t + 1) = d [a(t), x(t)].
- l является функцией выходов, определяющей значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, то есть, в момент y(t) = l[a(t), x(t)].
Когда множества А, Х и У являются конечными, то и автомат именуется конечным. Автомат функционирует следующим образом. В любой момент времени t он может находиться в некотором состоянии a(t) из множества А допустимых состояний, при этом в начальный момент времени t = 0 он должен находиться в состоянии a0. Автомат принимает входной сигнал x(t), формирует выходной сигнал y(t) = l[a(t), x(t)] и переходит в состояние a(t + 1) = d[a(t), x(t)]. Говоря иначе, абстрактный автомат любой паре символов a(t) и x(t) должен поставить в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы принято называть детерминированными.
Известны следующие условия преобразования информации в детерминированных автоматах:
- Каждое входное слово, длиною l букв, должно быть преобразовано в выходное слово той же длины.
- Если всякий раз перед подачей входного сигнала автомат находится в одном и том же состоянии, то в случае совпадения в двух входных словах первых l1 букв, в выходных словах первые l1 букв тоже должны совпасть.
Помимо детерминированных автоматов есть ещё вероятностные автоматы, в которых переход из одного состояния в другое под влиянием случайного или детерминированного входного сигнала осуществляется случайно. Работа подобных автоматов может быть описана уже матрицей переходов d, элементами которой выступают вероятности переходов из одного состояния в другое.
Детерминированные автоматы, используемые на практике, подразделяются на следующие классы:
- Автоматы Мили.
- Автоматы Мура.
Эти автоматы получили свои названия по именам американских ученых, которые впервые приступили к их изучению.
