При определении абстрактного автомата не учитывают физической природы входных и выходных сигналов, а рассматривают их как буквы некоторого алфавита.
Считают, что автомат функционирует в некотором идеализированном времени t = 0,1,2,…. При этих условиях автомат S определяется как шестикомпонентный кортеж.
– множество входных сигналов или входной алфавит.
– множество выходных сигналов или выходной алфавит.
– множество состояний.
δ – функция переходов. Она определяет следующее состояние автомата as = a(t+1) в момент времени (t+1) в зависимости от текущего состояния am и входного сигнала в момент времени t.
λ – функция выхода. По виду функции выхода автоматы делятся на автоматы Мили и автоматы Мура.
В автомате Мили λ ставит в соответствие паре состояний am– zf выходной сигнал wg.
wg = λ(am, zf) – функция выхода для автомата Мили.
В автомате Мура λ ставит в соответствие am выходной сигнал wg.
wg = λ(am) – функция выхода для автомата Мура.
Автомат называется конечным, если множества Z, W и A являются конечными.
|
|
Комбинационная схема описывается тройкой (вектором) S следующего вида:
.
Конечный автомат рассматривается как автомат с одним состоянием.
Автомат – детерминированный, если в нем выполняется условие однозначности, т.е. из состояния am он может перейти только в одно состояние под действием одного и того же входного сигнала.
Автомат Мили описывается выражениями:
.
Автомат Мура описывается как: