Основные понятия теории автоматов
Термин "автомат" используется в двух аспектах. С одной стороны, автомат – устройство, выполняющее некоторые функции без участия человека (например, ЭВМ). С другой стороны, термин "автомат" – математическое понятие и обозначает математическую модель реальных технических процессов.
В общем случае автомат представляется как "черный ящик" и полностью описывается совокупностью следующих шести объектов:
1) множество входных сигналов Х;
2) множество выходных сигналов Y;
3) множество состояний автомата А;
4) начальное состояние автомата a0 как элемент множества А;
5) функция перехода из одного состояния в другое f (a, x);
6) функция выходов автомата 
.
Автомат называется конечным, если множество его внутренних состояний, входных и выходных сигналов – конечные множества.
Цифровой автомат – устройство, предназначенное для преобразования цифровой информации.
В начальный момент времени t 0автомат находится в состоянии a 0. В каждый момент времени t, определяемый интервалом дискретности, автомат под воздействием входного сигнала x (t) скачкообразно переходит из состояния ai (t) в состояние ai (t+ 1) и выдает соответствующий выходной сигнал y (t).
Понятие состояние автомата используется для описания систем, выходы которых зависят не только от входных сигналов в данный момент времени, но и от некоторой предистории, – сигналов, которые поступили на входы системы ранее, т. е. состояние – некоторая память о прошлом.
Цифровые автоматы делят на два класса – синхронные и асинхронные.
В синхронных автоматах моменты времени, в которые фиксируются состояния автомата, задаются специальным устройством – генератором синхроимпульсов.
В асинхронных автоматах моменты перехода автомата из одного состояния в другое заранее не определены и зависят от каких-то событий.
В зависимости от закона определения выходных сигналов синхронные автоматы делятся на автоматы Мили и автоматы Мура.
Для автомата Мили закон функционирования определяется следующими соотношениями:
(1.1)
Следующее состояние автомата Мили (состояние в момент времени t+ 1) зависит от состояния автомата 
в текущий момент времени 
и входного сигнала 
в текущий момент времени. Выходной сигнал в момент времени t определяется текущим внутренним состоянием и текущим входным сигналом .
Работа автомата Мура описывается соотношениями
(1.2)
Следующее состояние автомата Мура есть функция от текущего состояния и текущего входного сигнала , а выходной сигнал в текущий момент времени t зависит только от текущего внутреннего состояния .
Языки описания автоматов
Среди языков описания наиболее распространены таблицы и графы переходов и выходов.
Таблица переходов (выходов) представляет собой таблицу с двойным входом, строки которой нумерованы входными сигналами, а столбцы – состояниями. На пересечении указывается состояние, в которое переходит автомат (в таблице переходов) или выходной сигнал, выдаваемый им (в таблице выходов).
Ниже представлены таблица переходов (табл. 1.1.) и таблица выходов (табл. 1.2.) автомата Мили.
Таблица 1.1Таблица 1.2
| Входной сигнал | Внутреннее состояние | |||
| а 0 | а 1 | а 2 | а 3 | |
| х 1 | y 1 | y 3 | y 2 | y 3 |
| х 2 | y 1 | y 2 | y 3 | y 4 |
| Входной сигнал | Внутреннее состояние | |||
| а 0 | а 1 | а 2 | а 3 | |
| х 1 | а 1 | а 2 | а 3 | а 0 |
| х 2 | а 3 | а 2 | а 2 | а 1 |
Например, если автомат Мили в текущий момент времени находится в состоянии а 1 и на входе автомата присутствует входной сигнал х 1, то следующее состояние будет а 2 (см. табл. 1.1) и на выходе автомата будет присутствовать выходные сигналы y 1, y 3 (см. табл. 1.2).
Иногда при задании автомата Мили используют одну совмещенную таблицу переходов и выходов, в которой на пересечении столбца аi и строки хj записывают в виде аk /ym следующее состояние и выдаваемый выходной сигнал. Совмещенная таблица переходов и выходов автомата Мили, заданного табл. 1.1 и табл. 1.2, представлена в табл. 1.3.
Таблица 1.3
| Входной сигнал | Внутреннее состояние | |||
| а 0 | а 1 | а 2 | а 3 | |
| х 1 | а 1/ y 1 | а 2/ y 1, y 3 | а 3/ y 2 | а 0/ y 3 |
| х 2 | а 3/ y 1 | а 2/ y 2 | а 2/ y 3 | а 1/ y 4 |
Так как в автомате Мура выходной сигнал зависит только от состояния, автомат Мура задается одной отмеченной таблицей переходов (табл. 1.4), в которой каждому её столбцу приписан кроме состояния аi ещё и выходной сигнал, соответствующий этому состоянию. Например, автомат Мура, заданный табл. 1.4, находясь в состоянии а 2, выдает выходной сигнал у 1 и при поступлении входного сигнала х 2 перейдет в следующее состояние – а 1.
Таблица 1.4
| Входной сигнал | Выходные сигналы | ||||
| y 2 | y 3 | y 1 | y 4 | y 5 | |
| Внутреннее состояние | |||||
| а 0 | а 1 | а 2 | а 3 | а 4 | |
| х 1 | а 1 | а 2 | а 3 | а 4 | а 0 |
| х 2 | а 3 | а 2 | а 1 | а 0 | а 4 |
Более наглядно и удобно автомат можно задать с помощью графа автомата. Граф автомата – ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Дугам автомата Мили приписывается входной сигнал, обеспечивающий данный переход и выходной сигнал, который при этом выдаётся. При описании автомата Мура в виде графа выходной сигнал, соответствующий данному состоянию, записывается внутри вершины или рядом с ней. На рис. 1.1 приведены графы автомата Мили (рис. 1.1, а) и автомата Мура (рис. 1.1, б), заданных табл. 1.3 и 1.4.
Рис. 1.1. Графы автоматов Мили (а) и Мура (б)
В графе автомата не должно существовать двух дуг с одинаковыми входными сигналами, выходящих из одной и той же вершины (условие однозначности).
Состояние автомата называетсятупиковым, если соответствующая вершина графа не содержит исходящих дуг, но имеет хотя бы одну входящую дугу.
Изолированным состоянием называется такое состояние, которому соответствует вершина графа, не имеющая как входящих, так и исходящих дуг.