| Под автоматом понимается устройство, самостоятельно производящее все операции. Автомат может быть представлен структурой, состоящей из элементов памяти и комбинационной схемы (рис. 9.1).
Состояние выхода автомата в каждый, рассматриваемый момент времени определяется не только состоянием входов в данный момент времени, но и внутренним состоянием схемы в момент подачи входных сигналов. В свою очередь, внутреннее состояние схемы зависит от состояния её входов в предшествующий момент времени, а, следовательно, определяется последовательностью поступления входных сигналов.
На входы комбинационной схемы поступают внешние сигналы  ,  , …,  , и внутренние сигналы  ,  , …,  , снимаемые с выхода, входящего в состав схемы, запоминающего устройства. Под воздействием сигналов , , …, и , , …, комбинационная схема формирует последовательность сигналов  ,  , …,  на выходе ДУ и внутренние сигналы  ,  , …,  , поступающие на входы запоминающего устройства.
|
Формализованное описание автомата называют его логической структурой. Свойства и методы преобразования логических структур изучает теория конечных автоматов, которая подразделяется на абстрактную и структурную. Абстрактная теория не затрагивает структуру самого автомата, ограничиваясь лишь рассмотрением переходов, претерпеваемых автоматом при изменении входных сигналов и изучением выходных сигналов, выдаваемых автоматом в каждом состоянии. Структурная теория изучает способы технической реализации структуры автомата с использованием конкретной элементной базы, а также способы кодирования его входных и выходных сигналов.
Автоматы можно подразделить на синхронные и асинхронные [1–4, 6, 9]. В синхронных автоматах переход из одного состояния в другое происходит под воздействием синхронизирующих сигналов. В асинхронных автоматах моменты перехода из одного состояния в другое заранее не определены и могут совершаться через неравные между собой промежутки времени.
Известны две модели синхронных элементарных автоматов: модель Мура и модель Мили, получивших названия по имени ученых, разработавших соответствующие разделы теории автоматов.
Моделью Мура называется автомат, описываемый уравнениями:
(9.1)
где S (t), S (t – 1) – состояния автомата в моменты времени t и t – 1;
X (t – 1), Z (t) – входные и выходные сигналы автомата в моменты времени t и t – 1.
Моделью Мили называется автомат, описываемый уравнениями:
(9.2)
Следовательно, состояние S (t) автомата, при его описании любой моделью, однозначно определяется его входными символами 
и внутренним состоянием 
в предшествующий момент времени: t – 1. Сигнал на выходе автомата у (t) в рассматриваемый момент времени t в модели Мура полностью определяется состоянием S (t) автомата в данный момент времени, а в модели Мили не только его внутренним состоянием S (t), но и состоянием входных сигналов.
Существует несколько способов представления конечных автоматов, основными из которых являются: графический, таблично-матричный и аналитический. Каждый из этих способов рассмотрим на конкретном примере описания автомата, осуществляющего последовательное включение двух устройств , , причем для включения второго устройства необходимо выполнить условие появления сигнала на входе 
раньше, чем на входе 
.
Графический способ предусматривает задание автомата направленным графом, вершинами которого являются состояния автомата, а ребрами – комбинации входных сигналов, вызывающие переход автомата из одного состояния в другое (рис. 9.2, а, б) [1–3, 6–9]. Петля при вершине графа свидетельствует о том, что данный входной сигнал не вызывает изменения состояния автомата. При задании автомата моделью Мура состояния выходов указываются непосредственно в узлах графа, так как полностью определяются внутренним состоянием автомата и не зависят от комбинации входных сигналов (рис. 9.2, а). В модели Мили выходные сигналы указываются над ребрами графа, рядом с комбинациями входных сигналов, так как определяются не только состоянием автомата, но и сигналами на его входе (рис. 9.2, б).
Рис. 9.2. Задание автомата графическим способом: а – при описании автомата моделью Мура; б – моделью Мили
Таблично-матричный способ предусматривает задание автомата путём записи всей необходимой информации о его функционировании в специальные автоматные таблицы, называемые таблицей переходов и таблицей выходов (рис. 9.3).
Рис. 9.3. Задание автомата графическим способом: а – при описании автомата моделью Мура; б – моделью Мили
На пересечении строк и столбцов автоматных таблиц соответственно указываются внутренние состояния, в которые переходит автомат под действием входных сигналов и выходные сигналы, которые он при этом выдает. Наряду с автоматными таблицами, при описании автоматов широко используются матрицы соединений. Число строк и столбцов данной матрицы соответствует числу состояний автомата, а на пересечении j -й строки и k -го столбца указываются комбинации входных сигналов, приводящие к переходу автомата из состояния j в состояние k.
Аналитический способ предусматривает задание автомата системой секвенциальных уравнений, называемой секвенциальным описанием автомата и составляемой на основе графа или автоматных таблиц:
| для модели Мура | для модели Мили | ||
| 
|
| 
|
| 
|
| 
|
| 
|
| 
|
|
| 
|
|
|
| 
| 
| 
|
|
| 
| ||
   .
|  .
|
Каждое такое уравнение представляет собой запись вида 
, означающую, что истинность утверждения a однозначно предопределяет истинность утверждения b. При составлении секвенциальных уравнений отдельно описываются совершаемые автоматом переходы и формируемые в каждом состоянии символы (сигналы) на выходе автомата.
Приведенные секвенции являются элементарными, так как каждая из них описывает всего один переход таблицы переходов или всего одну функцию таблицы выходов. Для уменьшения громоздкости описания автомата целесообразно использовать сокращенные секвенции, переходя к ним от элементарных посредством объединения левой и правой частей нескольких секвенций. Полученные для рассматриваемого автомата сокращенные секвенции имеют вид:
Для модели Мура
Для модели Мили
.
С целью получения наиболее простого выражения, сокращенные секвенции подвергаются минимизации, при выполнении которой необходимо проверять, чтобы получаемые в процессе преобразований секвенции не противоречили друг другу. Полученные для рассматриваемого автомата сокращенные секвенции имеют вид:
| для модели Мура | для модели Мили |
| 
|
| 
|
| 
|
|
| .
|
В качестве примера рассмотрим реализацию в базисе «И–НЕ» автомата заданного моделью Мура (см. рис. 9.2, а). Полученные для рассматриваемого автомата сокращенные секвенции имеют вид:
 ;
|
 ;
|
 ;
|
 ;  .
|
Для построения на основе полученного секвенциального описания структуры автомата необходимо наличие двух блоков: 1) реализации переходов, определяющих состояния автомата, и 2) реализации функций выхода. Для управления элементами памяти синтезируемого автомата функции 
, 
, 
необходимо использовать в качестве переключающих сигналов. С целью уменьшения требуемого объема памяти, любому состоянию автомата удобно поставить в соответствие некоторую кодовую комбинацию, определяемую состоянием всех триггеров автомата (табл. 9.1).
Таблица 9.1
