Для этого множества будет три класса:
Q
(0)
1
=
{
?
e,
?
a
2
,
?
a
2
?
a
2
,
?
a
1
?
a
1
?
a
1
,
?
a
2
?
a
1
?
a
2
}
,
Q
(0)
2
=
{
?
a
1
,
?
a
1
?
a
2
,
?
a
1
?
a
2
?
a
2
,
?
a
2
?
a
2
?
a
1
}
,
Q
(0)
3
=
{
?
a
1
?
a
1
,
?
a
2
?
a
1
,
?
a
1
?
a
2
?
a
1
,
?
a
1
?
a
1
?
a
1
?
a
1
,
?
a
1
?
a
1
?
a
2
?
a
1
}
.
Сопоставим этим классам соответственно внутренние реакции
b
(0)
1
, b
(0)
2
, b
(0)
3
некоторого процесса
P
(0)
, построив для него функции
перехода и выхода точно так же, как для процесса
P
(
S
)
, но используя
классы
Q
(0)
1
, Q
(0)
2
, Q
(0)
3
. Тогда получим процесс, граф переходов кото-
рого показан на рис. 3. Этот процесс является недетерминированным,
так как из состояния
b
(0)
1
исходят две дуги, помеченные одним и тем
же восприятием
?
a
1
(переход по таким дугам из одного и того же
состояния осуществляется недетерминированно). Если с помощью
алгоритма 1 для того же множества
S
построить классы эквивалент-
ности, то их будет четыре:
Q
1
=
{
?
e,
?
a
2
?
a
2
}
,
Q
2
=
{
?
a
1
,
?
a
1
?
a
2
,
?
a
1
?
a
2
?
a
2
,
?
a
2
?
a
2
?
a
1
}
,
Q
3
=
{
?
a
1
?
a
1
,
?
a
2
?
a
1
,
?
a
1
?
a
2
?
a
1
,
?
a
1
?
a
1
?
a
1
?
a
1
,
?
a
1
?
a
1
?
a
2
?
a
1
}
,
Q
4
=
{
?
a
2
,
?
a
1
?
a
1
?
a
1
,
?
a
1
?
a
1
?
a
2
}
.
Сравнивая
Q
1
, Q
2
, Q
3
, Q
4
и
Q
(0)
1
, Q
(0)
2
, Q
(0)
3
, видим, что
Q
(0)
1
=
Q
1
∪
Q
4
,
Q
(0)
2
=
Q
2
, Q
(0)
3
=
Q
3
, т.е. для того чтобы по классам
Q
(0)
i
построить
граф переходов детерминированного процесса
P
(
S
)
(рис. 4), достаточ-
но разбить множество
Q
(0)
i
на два непересекающихся подмножества
Q
1
и
Q
4
. Эта процедура соответствует замене состояния
b
(0)
1
графа
переходов недетерминированного процесса
P
(0)
(см. рис. 3) двумя со-
Рис. 3. Граф переходов недетермини-
рованного процесса
P
(0)
Рис. 4. Граф переходов детерминиро-
ванного процесса
P
(1)
=
P
(
S
)
68 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012. № 4
