Изучение моделей конечных автоматов

Проектирование ДУ выполняется на основе моделей автоматов. Многообразие существующих типов моделей автоматов обусловлено разнообразием ДУ, обладающих общими основными свойствами:

– Дискретность внутренних и внешних сигналов. Сигналы в ДУ дискретны по уровню. В настоящее время наибольшее распространение получили бинарные (двоичные) сигналы – «0» и «1». Отсюда переменные, используемые в моделях ДУ для представления сигналов, также бинарные.

– Дискретность времени в процессе функционирования. Все изменения сигналов в ДУ происходят в дискретные моменты времени. Процесс функционирования ДУ во времени представляется как некоторая последовательность тактов.

– Наличие состояний. ДУ на любом такте функционирования характеризуется: состоянием входов, состоянием выходов и внутренним состоянием (комбинация состояния входа и внутреннего состояния представляет полное состояние дУ). Предполагается, что ДУ мгновенно переходит из одного состояния в другое.

Множество разнообразных ДУ может быть классифицировано по их типам:

– преобладающее число ДУ имеет конечное число состояний входов, выходов и внутренних состояний. Такие устройства составляют класс конечных ДУ;

– значительное количество ДУ не содержат внутренней памяти и являются ДУ комбинационного типа. В комбинационных ДУ набор выходных сигналов однозначно определяется набором входных сигналов;

– ДУ, содержащие внутреннюю память, являются ДУ с памятью или последовательностными дискретными устройствами. В таких ДУ набор значений выходных сигналов определяется не только набором входных сигналов, но и внутренним состоянием ДУ;

– ДУ, в которых изменения входных, выходных сигналов, а также внутренних состояний происходит в определенные моменты времени, определяемые генератором синхронизирующих сигналов, называются синхронными. В синхронных ДУ длительность такта, как правило постоянна. ДУ, в которых моменты изменения входных, выходных сигналов, а также внутренних состояний заранее не определены называют асинхронными.

4.1. Общая модель конечного автомата [4, с. 157].

В большинстве случаев ДУ являются конечными, то преобладающей в применении является модель конечного автомата.

Абстрактно конечный автомат (англ. finite automata) (А), можно представить как математическую схему, характеризующуюся пятью объектами:

(3)

 

где – множество входных символов (входной алфавит); – множество выходных символов (выходной алфавит); – множество внутренних состояний; – функция переходов; – функция выходов.

В соответствии с (3) конечный А с памятью представляется тремя множествами и двумя функциями.