1.6. Определение основной модели

Теперь можно дать точное определение класса систем, которые мы будем называть конечными автоматами. Для краткости в дальнейшем представителей этого класса будем называть просто автоматами.

Определение 1.1. Конечным автоматом М называется синхронная система с конечным входным алфавитом с конечным выходным алфавитом с конечным множеством состояний

и двумя характеристическими функциями :

где — соответственно входной символ, выходной символ и состояние автомата М в момент

В этой книге предполагается, что автомат М, как это следует из определения 1.1, является детерминированным, т. е. его характеристические функции полностью определены. За исключением главы 7, также предполагается, что автомат М без ограничений на входе, т. е. любой входной символ может быть подан на автомат М в любой момент времени Особый тип конечного автомата получается при условии, что

Такой автомат называется тривиальным автоматом . Промежуточные переменные в тривиальном автомате не оказывают действия на зависимость между входами и выходами и, следовательно, понятие состояния в этом случае оказывается лишним. Нетривиальным называется автомат, для которого