Рис. 6. Композиция автоматов
определенных автоматов отношения ре-
дукции и эквивалентности совпадают.
Автомат, который не имеет эквива-
лентных состояний, называется
приве-
денным
. Известно [9], что для каждого
автомата
A
существует эквивалентный
приведенный автомат, который называ-
ется
приведенной формой
автомата
A
.
Более того, для каждого недетерминиро-
ванного автомата также есть эквивалент-
ный
наблюдаемый
автомат
(
S, I, O, T, r
)
,
в котором для любой тройки
(
i, p, o
)
2
I
×
S
×
O
существует не более
одного состояния
n
2
S
такого, что
(
i, p, n, o
)
2
T
.
Рассмотренные модели различных автоматов можно объединить в
единую модель путем композиции. Рассмотрим композицию автоматов
A
и
B
на рис. 6. Автомат
A
имеет входной алфавит
I
×
V
и выходной
алфавит
U
×
O
; автомат
B
имеет входной алфавит
Y
×
U
и выходной
алфавит
V
×
Z
. Таким образом, язык автомата
A
есть
LA
(
I
×
V
×
×
U
×
O
)
, язык автомата
B
есть
L
A
(
Y
×
U
×
V
×
Z
)
.
Синхронная композиция (см. рис. 6) или просто композиция
A
•
B
автоматов
A
и
B
имеет входной алфавит
I
×
Y
и выходной алфавит
O
×
Z
. Входной-выходной символ
(
iyoz
)
2
I
×
Y
×
O
×
Z
принадле-
жит языку композиции, если и только если существует согласованная
пара внутренних символов
uv
2
U
×
V Z
таких, что
(
ivuo
)
2
L
A
и
(
yuvz
)
2
L
B
.
Синхронная композиция автоматов строится следующим образом.
Сначала язык автомата
A
расширяется на множество
Y
×
Z
и язык
автомата
B
расширяется на множество
I
×
O
посредством добавления
на каждом переходе всех возможных пар из алфавита расширения.
Полученные языки пересекаются и строится проекция пересечения на
алфавит композиции
I
×
Y
×
O
×
Z
. Приведенный наблюдаемый авто-
мат с полученным языком и называется композицией
A
•
B
автоматов
A
и
B
. Все операции над языками осуществляются на основе соответ-
ствующих известных методов [8]. В зависимости от типа автоматов
композиция может быть детерминированным или недетерминирован-
ным автоматом, полностью определенным или частичным автоматом.
Выводы.
Таким образом, можно утверждать, что рассмотренный
автоматный подход к формализации построения модели ИБ САПР
можно считать корректным и теоретически обоснованным. Практиче-
ская реализация синтезированного автомата возможна с использовани-
ем любых известных программных средств, например UML. Условия
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 3 73
