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