2015-02-27
364
Теперь можно дать точное определение класса систем, которые мы будем называть конечными автоматами. Для краткости в дальнейшем представителей этого класса будем называть просто автоматами.
Определение 1.1. Конечным автоматом М называется синхронная система с конечным входным алфавитом X = {ξ1, ξ1,..., ξp}, с конечным выходным алфавитом Z = {ζ1, ζ1,..., ζp}, с конечным множеством состояний
S= {σ1, σ2,..., σn} и двумя характеристическими функциями f z и f s:
z ν =f z (x ν, s ν), (1.5)
s ν+1 =fs (x ν, s ν), (1.6)
где x ν, z ν и s ν — соответственно входной символ, выходной символ и состояние автомата М в момент t ν(ν= I, 2,...)[3].
В этой книге предполагается, что автомат М, как это следует из определения 1.1, является детерминированным, т. е. его характеристические функции полностью определены. За исключением главы 7, также предполагается, что автомат М без ограничений на входе, т.е. любой входной символ может быть подан на автомат М в любой момент времени t ν.
Особый тип конечного автомата получается при условии, что
|
|
|
f z = (x ν, s ν) = f z (x ν), (1.7)
Такой автомат называется тривиальным автоматом[4]. Промежуточные переменные в тривиальном автомате не оказывают действия на зависимость между входами и выходами и, следовательно, понятие состояния в этом случае оказывается лишним. Нетривиальным называется автомат, которого
f z (x ν, s ν) ≠ f z (x ν), (1.8)
