Абстрактный автомат

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

Формально абстрактный автомат определяется как пятёрка





A
=
(
S
,
X
,
Y
,
δ
,
λ
)



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

Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом,




δ
:
S
×
X

S


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

— функция переходов,




λ
:
S
×
X

Y


{\displaystyle \lambda :S\times X\rightarrow Y}

— функция выходов.

Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом. Таким образом, абстрактный автомат определяет семейство инициальных автоматов





(

s

i


,
A
)
,

s

i



S



{\displaystyle {\boldsymbol {(s_{i},A),s_{i}\in S}}}

Если функции переходов и выходов однозначно определены для каждой пары





(
s
,
x
)

S
×
X



{\displaystyle {\boldsymbol {(s,x)\in S\times X}}}

, то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определённым.

Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным.

Ограничение числа состояний абстрактного автомата определило такое понятие как конечный автомат.

Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата






s

1


[
1
]

s

2


[
2
]

s

3


[
3
]
.
.
.



{\displaystyle {\boldsymbol {s_{1}[1]s_{2}[2]s_{3}[3]…}}}

и последовательности выходных символов






y

1


[
1
]

y

2


[
2
]

y

3


[
3
]
.
.
.



{\displaystyle {\boldsymbol {y_{1}[1]y_{2}[2]y_{3}[3]…}}}

, которые для последовательности символов






x

1


[
1
]

x

2


[
2
]

x

3


[
3
]
.
.
.



{\displaystyle {\boldsymbol {x_{1}[1]x_{2}[2]x_{3}[3]…}}}

разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:





s
(
t
+
1
)
=
δ
(
s
(
t
)
,
x
(
t
)
)
;



{\displaystyle {\boldsymbol {s(t+1)=\delta (s(t),x(t));}}}





y
(
t
)
=
λ
(
s
(
t
)
,
x
(
t
)
)
.



{\displaystyle {\boldsymbol {y(t)=\lambda (s(t),x(t)).}}}

Для уточнения свойств абстрактных автоматов введена классификация.

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

Модель абстрактного автомата широко используется, как базовая, для построения дискретных моделей автоматов, распознающих, порождающих и преобразующих последовательности символов.

Литература

  • Виктор Михайлович Глушков. Абстрактная теория автоматов. — Успехи математических наук, т. XVI, вып. 5 (101). — М., 1961. — С. 476.
  • Виктор Михайлович Глушков. Синтез цифровых автоматов. — М.: Государственное издательство физико-математической литературы, 1962. — С. 476.

Error: 404 Not Found.

Абстрактный автомат

Error: 404 Not Found.

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

Рассказать друзьям:
Смотреть:
Радиан