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

Ниже в тексте используются следующие обозначения:

$S$$S$ — множество состояний автомата

$X$$X$ — входной алфавит

$Y$$Y$ — выходной алфавит

$\mathrm{\delta <!--\; \delta \; -->}$$\delta$ — функция переходов

$\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$ — функция выходов

$S$$S$, $X$$X$, $Y$$Y$ — конечные непустые множества

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

По способу формирования функций выходов выделяют автоматы Мили и Мура.

Автомат МилиПравить

Основная статья: Автомат Мили

В автомате Мили (англ. Mealy machine) функция выходов $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата. Таким образом, можно дать следующее определение:

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

$\mathit{A}\mathbf{=}\mathbf{(}\mathit{S}\mathbf{,}\mathit{X}\mathbf{,}\mathit{Y}\mathbf{,}\mathit{\delta <!--\; \delta \; -->}\mathbf{,}\mathit{\lambda <!--\; \lambda \; -->}\mathbf{)}$${\boldsymbol {A=(S,X,Y,\delta ,\lambda )}}$ ,

где $S$$S$ , $X$$X$  и $Y$$Y$  — конечные непустые множества, а $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  и $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  — отображения вида:

$\mathrm{\delta <!--\; \delta \; -->}:S\times <!--\; \times \; -->X\to <!--\; \to \; -->S$$\delta :S\times X\rightarrow S$  и $\mathrm{\lambda <!--\; \lambda \; -->}:S\times <!--\; \times \; -->X\to <!--\; \to \; -->Y$$\lambda :S\times X\rightarrow Y$ 

со связью элементов множеств $S$$S$ , $X$$X$  и $Y$$Y$  в абстрактном времени $T$$T$  = 0, 1, 2, … уравнениями:

$\mathit{s}\mathbf{(}\mathit{t}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{=}\mathit{\delta <!--\; \delta \; -->}\mathbf{(}\mathit{s}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{,}\mathit{x}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{)}\mathbf{,}$${\boldsymbol {s(t+1)=\delta (s(t),x(t)),}}$ 

$\mathit{y}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{=}\mathit{\lambda <!--\; \lambda \; -->}\mathbf{(}\mathit{s}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{,}\mathit{x}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{)}\mathbf{,}\mathit{t}\mathbf{\in <!--\; \in \; -->}\mathit{T}$${\boldsymbol {y(t)=\lambda (s(t),x(t)),t\in T}}$ 

(Отображения $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  и $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  получили названия, соответственно функции переходов и функции выходов автомата A).

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

Автомат МураПравить

Основная статья: Автомат Мура

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

 

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

Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов: $\mathit{A}\mathbf{=}\mathbf{(}\mathit{S}\mathbf{,}\mathit{X}\mathbf{,}\mathit{Y}\mathbf{,}\mathit{\delta <!--\; \delta \; -->}\mathbf{,}\mathit{\mu <!--\; \mu \; -->}\mathbf{)}\mathbf{,}$${\boldsymbol {A=(S,X,Y,\delta ,\mu ),}}$ 

где $S$$S$ , $X$$X$ , $Y$$Y$  и $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  — соответствуют определению автомата типа Мили, а $\mathrm{\mu <!--\; \mu \; -->}$$\mu$  является отображением вида: μ : S → Y,

с зависимостью состояний и выходных сигналов во времени уравнением:

$\mathit{y}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{=}\mathit{\mu <!--\; \mu \; -->}\mathbf{(}\mathit{s}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{)}\mathbf{,}\mathit{t}\mathbf{\in <!--\; \in \; -->}\mathit{T}$${\boldsymbol {y(t)=\mu (s(t)),t\in T}}$ .

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

Для любого автомата Мура существует автомат Мили, реализующий ту же самую функцию. И наоборот: для любого автомата Мили существует соответствующий автомат Мура (возможно, со сдвигом по времени, т.е. $\mathrm{\mu <!--\; \mu \; -->}(s(t+1))=\mathrm{\lambda <!--\; \lambda \; -->}(s(t),x(t)),t\in <!--\; \in \; -->T$$\mu (s(t+1))=\lambda (s(t),x(t)),t\in T$ ).

Другие классы автоматовПравить

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

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

$\mathit{B}\mathbf{=}\mathbf{(}\mathit{S}\mathbf{,}\mathit{Y}\mathbf{,}\mathit{\gamma <!--\; \gamma \; -->}\mathbf{,}\mathit{\mu <!--\; \mu \; -->}\mathbf{)}$${\boldsymbol {B=(S,Y,\gamma ,\mu )}}$ ,

$\mathrm{\gamma <!--\; \gamma \; -->}:S\to <!--\; \to \; -->S$$\gamma :S\rightarrow S$ 

$\mathrm{\lambda <!--\; \lambda \; -->}:S\to <!--\; \to \; -->Y$$\lambda :S\rightarrow Y$ 

$\mathit{s}\mathbf{(}\mathit{t}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{=}\mathit{\gamma <!--\; \gamma \; -->}\mathbf{(}\mathit{s}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{)}\mathbf{,}$${\boldsymbol {s(t+1)=\gamma (s(t)),}}$ 

$\mathit{y}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{=}\mathit{\mu <!--\; \mu \; -->}\mathbf{(}\mathit{s}\mathbf{(}\mathit{t}\mathbf{)}\mathbf{)}\mathbf{,}\mathit{t}\mathbf{\in <!--\; \in \; -->}\mathit{T}$${\boldsymbol {y(t)=\mu (s(t)),t\in T}}$ 

где $S$$S$  и $Y$$Y$  — конечные непустые множества состояний и выходных сигналов, а $\mathit{\gamma <!--\; \gamma \; -->}$${\boldsymbol {\gamma }}$  и $\mathit{\mu <!--\; \mu \; -->}$${\boldsymbol {\mu }}$  — отображения выше указанного вида.

Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата.

Такой автомат получил название автономного конечного детерминированного автомата.

Для каждых начального состояния ${\mathit{s}\mathbf{(}\mathbf{0}\mathbf{)}\mathbf{=}{\mathit{s}}_{\mathit{i}}}_0$${\boldsymbol {s(0)={s_{i}}}}_{0}$  и натурального числа $t$$t$  автомат B определяет две последовательности:

${{\mathit{s}}_{\mathit{i}}}_0,{{\mathit{s}}_{\mathit{i}}}_1{\mathbf{=}\mathit{\gamma <!--\; \gamma \; -->}\mathbf{(}{\mathit{s}}_{\mathit{i}}}_0{\mathbf{)}\mathbf{,}{\mathit{s}}_{\mathit{i}}}_2{\mathbf{=}\mathit{\gamma <!--\; \gamma \; -->}\mathbf{(}{\mathit{s}}_{\mathit{i}}}_1{\mathbf{)}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{s}}_{\mathit{i}}}_t{\mathbf{=}\mathit{\gamma <!--\; \gamma \; -->}\mathbf{(}{\mathit{s}}_{\mathit{i}}}_{t-<!--\; -\; -->1}\mathbf{)}\mathbf{,}$${\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 {),}}$ 

${\mathit{\mu <!--\; \mu \; -->}\mathbf{(}{\mathit{s}}_{\mathit{i}}}_0{\mathbf{)}\mathbf{,}\mathit{\mu <!--\; \mu \; -->}\mathbf{(}{\mathit{s}}_{\mathit{i}}}_1{\mathbf{)}\mathbf{,}\mathit{\mu <!--\; \mu \; -->}\mathbf{(}{\mathit{s}}_{\mathit{i}}}_2{\mathbf{)}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathit{\mu <!--\; \mu \; -->}\mathbf{(}{\mathit{s}}_{\mathit{i}}}_{t-<!--\; -\; -->1}\mathbf{)}\mathbf{.}$${\boldsymbol {\mu ({s_{i}}}}_{0}{\boldsymbol {),\mu ({s_{i}}}}_{1}{\boldsymbol {),\mu ({s_{i}}}}_{2}{\boldsymbol {),...,\mu ({s_{i}}}}_{t-1}{\boldsymbol {).}}$ 

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

 

Функциональная схема порождающего автомата

Пусть $\mathit{Y}\mathbf{=}\mathbf{\varnothing <!--\; \varnothing \; -->}$${\boldsymbol {Y=\emptyset }}$ . Тогда математическая модель и система рекуррентных соотношений имеют вид:

$\mathit{C}\mathbf{=}\mathbf{(}\mathit{X}\mathbf{,}\mathit{S}\mathbf{,}\mathit{\delta <!--\; \delta \; -->}\mathbf{)}\mathbf{;}$${\boldsymbol {C=(X,S,\delta );}}$ 

$\mathit{\delta <!--\; \delta \; -->}\mathbf{:}\mathit{S}\mathbf{\times <!--\; \times \; -->}\mathit{X}\mathbf{\to <!--\; \to \; -->}\mathit{S}$${\boldsymbol {\delta :S\times X\rightarrow S}}$ 

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

По характеру отсчёта дискретного времени автоматы делятся на синхронные и асинхронные.

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

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

См. такжеПравить

• Конечный автомат
• Диаграмма состояний (теория автоматов)
• Теория автоматов
• Асинхронная логика

СсылкиПравить

• Автоматы Мура и Мили Архивная копия от 24 августа 2019 на Wayback Machine // Викиконспекты Университета ИТМО
• Двусторонний детерминированный конечный автомат Архивная копия от 25 октября 2019 на Wayback Machine // Викиконспекты Университета ИТМО