Термин «автомат», как правило, используется в двух аспектах. С одной стороны, автомат - это устройство, выполняющее некоторые функции без непосредственного участия человека. С другой стороны, термин «автомат» обозначает математическую модель реальных технических автоматов, т.е. представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний, которые он может изменять мгновенно. Устройства, служащие для преобразования дискретной информации, называются дискретными (цифровыми) автоматами. Их делят на синхронные и асинхронные. В синхронных автоматах моменты времени, в которые оказывается возможным изменение состояния автомата, определяются специальным устройством – генератором синхронизирующих импульсов. Соседние моменты времени оказываются при этом обычно разделенными равными временными промежутками. Автомат называется конечным, если множество его внутренних состояний и множество значений входных сигналов – конечные множества. Конечные автоматы разделяют на автоматы без памяти и автоматы с памятью. Автоматом с памятью называют автомат, описываемый функциями переходов и выходов, оператор которого является оператором с памятью. Выходные слова автомата с памятью зависят не только от входных слов, но и от последовательности их поступления. Автомат с памятью имеет множество внутренних состояний, в которое он переходит под воздействием слов входного алфавита. Наличие множества внутренних состояний придает автомату способность запоминания входной информации, поступившей на вход автомата в прошлом.
Любой абстрактный автомат задается совокупностью из 6 объектов:
A=(X, Y, Q, q0, ?, ? )
где Х – конечное множество входных сигналов, называемое входным алфавитом автомата;
Y – конечное множество выходных сигналов, называемое выходным алфавитом автомата;
Q – произвольное множество, называемое множеством состояний автомата;
q0 – элемент из множества Q, называемый начальным состоянием автомата;
?(q, x), ?(q, x) - две функции, задающие однозначные отображения множества пар (q, x), где q?Q и x?X, в множества Q и Х. Функция ?(q, x) называется функцией переходов автомата, а функция ?(q, x) – функцией выходов, либо сдвинутой функцией выходов.
Автомат, заданный функцией выходов, называется автоматом первого рода, автомат, заданный сдвинутой функцией выходов, – автоматом второго рода.
В зависимости от вида функции выходов автоматы с памятью делятся на автоматы Мили и автоматы Мура.
Автоматами Мура называют такие автоматы, у которых выходной сигнал Y(t) не зависит явно от входного сигнала X(t) , а определяется лишь внутренним состоянием автомата в момент времени t. Автомат Мура задается уравнениями:
В данной системе уравнений первая строка есть функция перехода, вторая – функция выхода.
В автомате Мили выходной сигнал в момент времени t, зависит как от внутреннего состояния автомата в момент t, так и от входного сигнала в момент времени t.
