Конечный автомат является имеющим вход и выход устройством, ко-
торое может находиться в одном из своих состояний. Конечный автомат
осуществляет преобразование информации в дискретные моменты времени
0
,
1
,
2
, . . . , t, . . .
На вход автомата поступает последовательность символов
входного алфавита
X =
{
X
1
, X
2
, . . . , X
N
}
; эту последовательность называ-
ют входным словом. Функционирование конечного автомата осуществляется
в соответствии с системой из
NS
команд, где
S
– мощность алфавита состо-
яний
Q =
{
Q
1
, Q
2
, . . . , Q
S
}
. Значение выхода автомата является элементом
выходного алфавита
Y =
{
Y
1
, Y
2
, . . . , Y
M
}
. Каждая команда имеет следую-
щий вид:
X
i
Q
j
→
Y
k
Q
l
, где
X
i
— входная буква,
Q
j
— текущее состояние,
Y
k
— выходная буква и
Q
l
— состояние в следующий за текущим моментом
момент времени (следующее состояние).
Функционирование конечного автомата задают также кортежем
<
X
,
Y
,
Q
, V, P >,
где
V
:
X
×
Q
→
Y
(функция выхода);
P
:
X
×
Q
→
Q
(функция переходов).
Конечный автомат с определенным состоянием в начальный момент вре-
мени называется инициальным автоматом. В соответствии со своей системой
команд инициальный автомат реализует автоматную функцию, которая про-
извольное входное слово преобразует в выходное слово той же длины.
Трахтенброт Б.А. [2, 3] показал, что любой конечный автомат можно ре-
ализовать схемой, элементами которой являются функциональные элементы
и элементы единичной задержки. При некоторых соотношениях между пара-
метрами конечного автомата (N, M и S) эта реализация является асимптоти-
чески наилучшей. Отметим, что в случае произвольных автоматных базисов
реализация существенно усложняется [4—6]. Возможна зависимость слож-
ности реализации от весов нескольких элементов базиса; задача нахождения
асимптотически наилучшей реализации алгоритмически неразрешима.
Для реализации автомата M в рассматриваемом базисе буквы алфавитов
X
,
Y
и
Q
кодируют двоичными наборами длин
n
,
m
и
s
соответственно.
При этом кодировании функции
V
(функции
P
)
соответствует система
m
(система
s
) булевых функций от
n
+
s
переменных.
Имеющую
k
входов и
r
входов схему называют (
k, r
)-блоком.
Согласно Б.А. Трахтенброту, схема
S
, реализующая автомат M, имеет
n
входов
x
1
, x
2
, . . . , x
n
,
m
выходов
y
1
, y
2
, . . . , y
m
и состоит из (
n
+
s, m
)-
блока
A
, (
n
+
s, s
)-блока
B
и
s
элементов задержки. Здесь
n
=] log
2
N
[
,
m
=] log
2
M
[
и
s
=] log
2
S
[
. Блок
A
(блок
B
) реализует функцию выхода
(функцию переходов). Входы схемы
S
соединены с первыми входами блоков
A
и
B
. Остальные входы этих блоков соединены с выходами
s
элементов
задержки. Входы элементов задержки соединены с последними
s
выходами
блока
B
. Выходами схемы
S
являются выходы блока
A
.
Покажем, что любой конечный автомат можно реализовать схемой, в
которой все элементы памяти находятся в одном ОРС.
Через
Z
обозначим (2, 1)-блок, состоящий из (2, 1)-элемента
D
, реали-
зующего сложение по модулю два, и элемента задержки. Выход элемента
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2 99
