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

Материал из Википедии — свободной энциклопедии

Эта статья или раздел нуждается в переработке.
Пожалуйста, улучшите её в соответствии с правилами написания статей.

[править] Классификация автоматов по логическим свойствам функций переходов и выходов

По способу формирования функций выходов выделяют автоматы Мили и Мура. В автомате Мили функция выходов $λ$ определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата. Таким образом, можно дать следующее определение:

Конечным детерминированным автоматом типа Мили называется совокупность пяти объектов

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

где S, X и Y — конечные непустые множества, а $δ$ и $λ$ — отображения вида:

$\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}$

(Отображения $δ$ и $λ$ получили названия, соответственно функции переходов и функции выходов автомата A).

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

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

Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов: $\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).

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

Пусть |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}$

[править] Классификация автоматов по характеру отсчёта дискретного времени

По характеру отсчёта дискретного времени автоматы делятся на синхронные и асинхронные. В синхронных конечных автоматах моменты времени, в которые автомат считывает входные сигналы, определяются принудительно синхронизирующими сигналами. После очередного синхронизирующего сигнала с учётом «считанного» и в соответствии с соотношениями для функционирования автомата происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. Асинхронный конечный автомат считывает входной сигнал непрерывно, и поэтому, реагирую на достаточно длинный входной сигнал постоянной величины x, он может, как следует из соотношений для функционирования автомата, несколько раз изменять состояние, выдавая соответствующее число выходных сигналов, пока не перейдёт в устойчивое состояние, которое уже не может быть изменено данным входным сигналом.