Конечные автоматы.
Если выходные сигналы схемы в момент времени t зависят только от входных сигналов поступивших на схему в момент времени t, то такая схема называется комбинационной схемой. Пример:
&
A(t)
1
B(t)
Y(t)=A(t)*B(t)+C(t)
C(t)
В отличие от комбинационных схем у конечного автомата выходной сигнал схемы в момент времени t зависит не только от входных сигналов поступивших в момент времени t, но и от сигналов в предшествующие моменты времени. Предшествующие внешние воздействия запоминаются автоматом путем изменения его внутреннего состояния. Часть автомата, хранящую конкретное состояние называют внутренней памятью конечного автомата.
Основное качество, отличающее конечный автомат от других устройств – наличие дискретного счетного множества внутренних состояний и свойство скачкообразного перехода из одного состояния в другое. Моменты перехода из одного состояния в другое определяются генератором синхроимпульсов. Изменение состояния происходит под действием входных сигналов, которые возникают вне автомата и поступают к нему по конечному числу входных каналов. Результатом работы автомата является выдача выходных сигналов во внешние цепи по конечному числу выходных каналов.
Общая теория конечных автоматов может быть разбита на две части:
-абстрактная теория,
-структурная теория.
В абстрактной теории рассматриваются вопросы функционирования конечного автомата. На этом этапе автомат рассматривают как черный ящик, внутренняя структура которого не известна.
В структурной теории рассматривается внутренняя структура конечного автомата.
Абстрактный конечный автомат
Абстрактный
конечный автомат – это математическая
модель автомата, задаваемая множеством
из семи элементов:
,
где
–множество
внутренних состояний (алфавит
состояний),
– начальное
состояние конечного
автомата,
– множество
входных сигналов (входной
алфавит),
– множество
выходных сигналов 1-го рода
(выходной алфавит 1-го рода),
– множество
выходных сигналов 2-го рода
(выходной алфавит 2-го рода),
– функция
переходов.
Функция
переходов показывает, в какое состояние
переключится автомат в следующий момент
времени, если в данный момент времени
автомат находился в состоянии
,
а на вход поступал сигнал
:
.
– функция
выходов 1-го рода, которая
показывает, какой выходной сигнал 1-го
рода сформируется на выходе 1-го рода в
данный момент времени, если в данный
момент времени автомат находился в
состоянии a(t),
а на вход поступал сигнал z(t):
.
– функция
выходов 2-го рода
показывает, какой выходной сигнал 2-го
рода сформируется на выходе 2-го рода в
данный момент времени, если в
данный
момент времени автомат находился в
состоянии
,
а на вход поступал сигнал
:
.
В общем случае абстрактный автомат имеет 1 входной и 2 выходных канала. Такой автомат называют С-автоматом.
В
каждый момент времени
автомат находится в определенном
состоянии
.
При
- в начальном состоянии
.
Автомат,
находящийся в состоянии
воспринимает входной сигнал
,
выдает на выход 1-го рода сигнал
,
выдает на выход 2-го рода сигнал
и переходит в следующий момент времени
в состояние
.
.
Типы конечных автоматов.
Кроме рассмотренного выше С-автомата на практике получили распространение автоматы Мили и автоматы Мура.
Автомат Мили
Выходные сигналы автомата Мили - сигналы первого рода. Память автомата характеризуется множеством внутренних состояний автомата. Указывается (обязательно) состояние с которого автомат начинает работу - начальное состояние.
Алгоритм работы задается функцией переходов и функцией выходов первого рода:
.
Автомат Мура
Выходные сигналы автомата Мура - сигналы второго рода. Алгоритм работы задается функцией переходов и функцией выходов второго рода:
