Класифікація абстрактних автоматів


1. Класифікація автоматів по логічним властивостям функцій переходів і виходів

За способом формування функцій виходів виділяють автомати Мілі і Мура.

1.1. Автомат Мілі

В автоматі Мілі ( англ. Mealy machine ) Функція виходів \ Lambda визначає значення вихідного символу за класичною схемою абстрактного автомата. Математична модель автомата Мілі і схема рекурентних співвідношень не відрізняються від математичної моделі та схеми рекурентних співвідношень абстрактного автомата. Таким чином, можна дати наступне визначення:

Кінцевим детермінованим автоматом типу Мілі називається сукупність п'яти об'єктів

\ Boldsymbol {A = (S, X, Y, \ delta, \ lambda)} ,

де S, X і Y - кінцеві непорожні множини, а \ Delta і \ Lambda - Відображення виду:

\ Delta: S \ times X \ rightarrow S і \ Lambda: S \ times X \ rightarrow Y

зі зв'язком елементів множин S, X і Y в абстрактному часу T = {0, 1, 2, ...} рівняннями:

\ Boldsymbol {s (t +1) = \ delta (s (t), x (t)),}

\ Boldsymbol {y (t) = \ lambda (s (t), x (t)), t \ in T}

(Відображення \ Delta і \ Lambda отримали назви, відповідно функції переходів і функції виходів автомата A).

Особливістю автомата Мілі є те, що функція виходів є двухаргументной і символ у вихідному каналі y (t) виявляється тільки при наявності символу у вхідному каналі x (t). Функціональна схема не відрізняється від схеми абстрактного автомата.


1.2. Автомат Мура

Залежність вихідного сигналу тільки від стану представлена ​​в автоматах типу Мура ( англ. Moore machine ). В автоматі Мура функція виходів визначає значення вихідного символу тільки по одному аргументу - станом автомата. Цю функцію називають також функцією міток, так як вона кожному стану автомата ставить мітку на виході.

Функціональна схема автомата Мура

Кінцевим детермінованим автоматом типу Мура називається сукупність п'яти об'єктів: \ Boldsymbol {A = (S, X, Y, \ delta, \ mu),}

де S, X, Y і δ - відповідають визначенню автомата типу Мілі, а μ є відображенням виду: μ: S → Y,

із залежністю станів і вихідних сигналів у часі рівнянням:

\ Boldsymbol {y (t) = \ mu (s (t)), t \ in T} .


Особливістю автомата Мура є те, що символ y (t) в вихідному каналі існує весь час, поки автомат знаходиться в стані s (t).

Для будь-якого автомата Мура існує автомат Мілі, який реалізує ту ж саму функцію. І навпаки: для будь-якого автомата Мілі існує відповідний автомат Мура.


1.3. Інші класи автоматів

Цікаво виділити особливі класи автоматів, математичні моделі яких спираються тільки на два носія алгебри.

Нехай | X | = 1. Тоді математична модель і система рекурентних співвідношень мають вигляд:

\ Boldsymbol {B = (S, Y, \ gamma, \ mu)} ,

\ Gamma: S \ rightarrow S

\ Lambda: S \ rightarrow Y

\ Boldsymbol {s (t +1) = \ gamma (s (t)),}

\ Boldsymbol {y (t) = \ mu (s (t)), t \ in T}

де S і Y - кінцеві непорожні множини станів і в и ходних сигналів, а \ Boldsymbol {\ gamma} і \ Boldsymbol {\ mu} - Відображення вище зазначеного виду. Особливістю функціонування такого автомата є генерація послідовності символів вихідного слова тільки в залежності від послідовності станів автомата. Такий автомат отримав назву автономного кінцевого детермінованого автомата.

Для кожних початкового стану \ Boldsymbol {s (0) = {s_i}} _0 і натурального числа t автомат B визначає дві послідовності:

\ Boldsymbol {{s_i}} _0, \ boldsymbol {{s_i}} _1 \ boldsymbol {= \ gamma ({s_i}} _0 \ boldsymbol {), {s_i}} _2 \ boldsymbol {= \ gamma ({s_i}} _1 \ boldsymbol {), ..., {s_i}} _t \ boldsymbol {= \ gamma ({s_i}} _ {t-1} \ boldsymbol {),}

\ Boldsymbol {\ mu ({s_i}} _0 \ boldsymbol {), \ mu ({s_i}} _1 \ boldsymbol {), \ mu ({s_i}} _2 \ boldsymbol {), ..., \ mu ({ s_i}} _ {t-1} \ boldsymbol {).}

Кінцевий автомат може бути представлений як перетворювач вхідних послідовностей у вихідні. При цьому вихідні послідовності можуть розглядатися як породжуються, а вхідні - як представляються. Вихідні послідовності автомата визначають безліч слів, породжуваних цих автоматом. Автономний КДА називається породжує, якщо породжене їм слово представлене як вихідна послідовність, при цьому така послідовність називається породжуваної даними автоматом.

Функціональна схема породжує автомата

Нехай \ Boldsymbol {Y = \ empty} . Тоді математична модель і система рекурентних співвідношень мають вигляд:

\ Boldsymbol {C = (X, S, \ delta);}

\ Boldsymbol {\ delta: S \ times X \ rightarrow S}


2. Класифікація автоматів за характером відліку дискретного часу

За характером відліку дискретного часу автомати поділяються на синхронні і асинхронні.

У синхронних кінцевих автоматах моменти часу, в які автомат зчитує вхідні сигнали, визначаються примусово синхронизирующими сигналами. Після чергового синхронізуючого сигналу з урахуванням "зчитаного" і відповідно до співвідношеннями для функціонування автомата відбувається перехід у новий стан і видача сигналу на виході, після чого автомат може сприймати таке значення вхідного сигналу.

Асинхронний кінцевий автомат зчитує вхідний сигнал безперервно, і тому, реагуючи на досить довгий вхідний сигнал постійної величини x, він може, як випливає з співвідношень для функціонування автомата, кілька разів змінювати стан, видаючи відповідне число вихідних сигналів, поки не перейде в стійкий стан, яке вже не може бути змінене даними вхідним сигналом.