Очевидно, что трудоемкость алгоритма 2 не больше, чем трудо-
емкость алгоритма 1, но практически может быть существенно мень-
ше, если число недетерминированных состояний невелико или быстро
падает.
В случае задания процесса множеством рекурсивных канониче-
ских процессных выражений множество нитей
S
задается неявно,
множество состояний процесса вводится непосредственно при опи-
сании и может быть далеко не оптимальным. Алгоритм 2 может быть
легко модифицирован для работы непосредственно с каноническими
процессными выражениями, позволяя оптимизировать процесс, опи-
сываемый таким образом. Идея этой модификации проста. Алгоритм 2
последовательно разбивает классы
Q
(
i
)
1
, Q
(
i
)
2
, . . . , Q
(
i
)
k
i
множества
?
S
, с
которыми сопоставляются состояния
b
(
i
)
1
, b
(
i
)
2
, . . . , b
(
i
)
k
i
процесса
P
(
i
)
, на
подклассы
Q
(
i
+1)
1
, Q
(
i
+1)
2
, . . . , Q
(
i
+1)
k
i
+1
, с которыми сопоставляются со-
стояния
b
(
i
+1)
1
, b
(
i
+1)
2
, . . . , b
(
i
+1)
k
i
+1
процесса
P
(
i
+1)
. Это осуществляется до
тех пор, пока очередной процесс не станет детерминированным. По-
сле этого в множестве
?
S
уже нет никакой необходимости — получен
оптимальный процесс. Он оптимален, поскольку нельзя объединить
в одно состояние ни одной пары его состояний, так как в этом слу-
чае получим недетерминированный процесс. Если же описание про-
цесса, например на языке канонических процессных выражений, не-
оптимальное, то какие-то состояния процесса могут быть объединены
в одно, поскольку они эквивалентны, т.е. при объединении этих со-
стояний в одно процесс остается детерминированным. Проверка же
на детерминированность может осуществляться аналогично тому, как
это делается в алгоритме 2, но не по множеству нитей
?
S
, которого у
нас в явном виде нет, а путем использования процессных выражений,
которые неявно это множество задают. Сформулируем этот алгоритм.
Алгоритм 3
:
а) принять
r
= 1
, s
= 0
;
б) сформировать процессное выражение
b
(
s
)
r
=
b
i
1
|
b
i
2
|
. . .
|
b
i
l
из
всех состояний
b
i
j
, для которых внешняя реакция
!
a
во внешних про-
цессных выражениях
!
a
=
b
i
j
одна и та же;
в) если имеются состояния, не вошедшие ни в одно процессное
выражение
b
(
s
)
r
, то принять
r
=
r
+ 1
и перейти к п. “б”. В противном
случае перейти к п. “г”;
г) получить процессные выражения
B
(
s
)
k
, k
= 1
,
2
, . . . , r
, подста-
новкой в процессное выражение
b
(
s
)
k
=
b
i
1
|
b
i
2
|
. . .
|
b
i
l
вместо каждого
состояния
b
i
j
правой части соответствующего процессного выражения
b
i
j
. Принять
j
= 1
, A
(
s
)
j
=
?
;
д) поместить
b
(
s
)
j
в множество
A
(
s
)
j
;
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012. № 4 71
