Файл: Математические основы теории систем.pdf

101
Z=N×X×Y; (2.4.37)
Q=V×W; (2.4.38)
M=L×T; (2.4.39)
(
)
( / )
( / )
n t l
n l t
n N t T
l L
Kq
F
v P
w
∈
∈
∈




=
×






∪ ∪
. (2.4.40)
Используя соотношения (2.4.37) – (2.4.40), можно показать, что опе- рация композиции ассоциативна и с точностью до изоморфизма комму- тативна, и, следовательно, множество произвольных автоматов и задан- ная на этом множестве операция композиции образует коммутативную полугруппу
B

В частных случаях операция композиции соответствует рассмотрен- ным ранее операциям умножения, суммирования, суперпозиции.
Например, пусть
A=(X,V,L, v
1
∈V, F(x∈X/l∈L)) и B=(Y,W,T, w
1
∈W,
P(y∈Y/t∈T))– независимо работающие автоматы. Так как автоматы име- ют различные входные алфавиты (
Х∩Y=Ø), пользуемся формулами
(2.4.30) – (2.4.33). Отображение
F состояния v∈V автомата А не зависит от выхода автомата
В, а отображение P состояния w∈W автомата В не зависит от выхода автомата
А, поэтому
/
t l
l L
t T
F v Fv
∈
∈
=
∪
,
/
l t
l L
t T
P w Pw
∈
∈
=
∪
Окончательно автомат
C=(Z,Q,M, q
1
∈Q, K(z∈Z/m∈M)) определяется по формулам
Z=X×Y, Q=V×W, M=L×T, Kq=Fv×Pw, которые совпадают с формулами (2.4.13) – (2.4.16) и, следовательно, за- дают операцию умножения ×.
Нетрудно для частных случаев перейти от композиции и к другим ал- гебраическим операциям: умножению автоматов с общим выходом, су- перпозиции и суммированию.
2.4.3. Операции над вероятностными автоматами
Автоматы, которые до сих пор рассматривались, можно отнести к не- случайным или детерминированным автоматам в том смысле, что состо-

102 яния таких автоматов в текущий момент времени однозначно определя- лось состоянием в предшествующий момент времени и буквами входного и выходного алфавитов в текущий момент времени. Наряду с такими ав- томатами естественно было бы рассматривать вероятностные автоматы, в которых переход из состояния в состояние носил бы стохастический или вероятностный характер. В реальных ситуациях это возможно из-за сбоев электронных схем при различного рода помехах.
Для простоты изложения рассмотрим вероятностные автоматы без выходов.
Вероятностный автомат считается заданным, если определена сово- купность объектов:
А=(Х,Q, q
1
∈Q, ϕ(q, x)), где
Х={х
1
,
х
2
,
… х
m
} – как обычно, входной алфавит,
Q={q
1
,
q
2
,
… q
n
} – алфавит состояний,
q
1
∈Q – начальное состояние автомата, ϕ(q, x)– дву- местная функция, задающая отображение множества
Q×X в множество матриц P={P
j
},
i={1, 2, … m}.
Эта функция ϕ(
q, x) называется таблицей переходных вероятностей.
Для каждой пары (
q, x) такой таблицы имеет место
ϕ(q,x)={p
1
(
q,x), p
2
(
q, x), … p
n
(
q,x)}, (2.4.41) где
p
i
(
q, x) означает вероятность перехода в состояние q
i
из состояния q по входной букве
х и, следовательно, является неотрицательной величи- ной
p
i
(
q, x)≥0 и удовлетворяет условию нормировки
(1,... )
( , ) 1
i
i
n
p q x
=
=
∑
Из записи (2.4.41) следует, что любая матрица
P
j
∈P имеет вид
P
j
=
║p
ik
(
x)║ или, что то же самое, P
j
=
║p
k
(
q
i
,
x)║, где i, k∈{1, 2, … n}. Все элементы
p
ik
каждой из матриц суть неотрицательные вещественные чис- ла, не превосходящие единицы, и сумма элементов любой из строк равна единице. Предполагается также, что в автомате нет состояний, вероятно- сти перехода в которые из всех других состояний равны нулю (т.е. нет столбцов, состоящих из одних нулей). Матрицы с такими свойствами называются стохастическими матрицами.
Если вероятностные автоматы рассматриваются в плане представле- ния событий, то, как и для детерминированных автоматов, задается мно- жество заключительных состояний
Q
z
⊆Q.
В вероятностном автомате можно вместо функции ϕ(
q, x) задать мно- жество стохастических матриц P
. Тогда он будет записан в форме
A=(X,Q,q
1
∈Q, P).

103
Обычный недетерминированный автомат можно рассматривать как частный случай вероятностного автомата, в котором для любого фикси- рованного
i∈{1, 2, … n} только одна из вероятностей p
ik
(
x) равна едини- це, а остальные равны нулю.
Нетрудно подсчитать вероятность перехода из некоторого состояния
q
i
в состояние
q
k
при поступлении на вход вероятностного автомата слова
х∈
Х*. Действительно, пусть
1 2
j
j
j l
x x
x
=
x
. Тогда вероятности перехода
( )
i k
p x вычисляются умножением стохастических матриц
1 2
j
j
j l
P P
P
:
( )
1 2
j
j
j l
i k
p
=
⋅
⋅ ⋅
=
P P P
P
x , где
i, k∈{1, 2, … n}.
В последнем выражении применено обычное умножение (строка на столбец) матриц, которое допустимо, поскольку матрицы
i k
P согласова- ны по форме (все они квадратные размерности
n× n).
Пример 2.21.
Задан вероятностный автомат
(
)
1
, ,
,
A
X Q q
Q
=
∈
P , где
1 2
1 1 0 1 2 2 ,
1 2 3 1 3 3 4 4
x
x








=
=














P
P
Найдем вероятность перехода автомата из состояния
q
1
в состояние
q
2
при поступлении на вход автомата слова x=
x
1
x
1
x
2
. Последовательно пе- ремножая матрицы
1 1
2
,
и
x
x
x
P P
P , получаем
1 1
5 3
1 1 1 1 8
8 2 2 2 2 3 1 3 1 9
7 4 4 4 4 16 16
x
x



 




 



⋅
=
⋅
=

 




 


 
 


 
 

P P
,
1 1
2 5
3 1
7 0 1 8
8 8
8 1 2 9
7 7
41 3 3 16 16 48 48
x
x
x
















=
⋅
⋅
=
×
=


















x
P
P P P

104
Искомая вероятность – это элемент первой строки и второго столбца последней матрицы, т.е.
7 8
Если
Q
z
={
q
α
},
α∈I
'
={1, 2, …
k} – множество заключительных состоя- ний, то вероятность
1
( )
( )
I
p
p
α
′
α∈
= ∑
x
x есть вероятность того, что автомат из начального состояния
q
1
перейдет в одно из заключительных состояний
q∈Q
z
при подаче на вход автомата слова
х.
Вероятностные автоматы можно задавать графами переходов, как и детерминированные автоматы, только нужно около каждого ребра, свя- зывающего вершины
q
i
с
q
j
, ставить кроме буквы входного алфавита
х
еще и соответствующую вероятность перехода
p
ij
(
x). Понятно, что анали- тический способ создания автоматов (2.4.41) и геометрическая интерпре- тация в виде графа неудобны и громоздки даже при небольшом числе букв входного алфавита, поэтому вероятностный автомат задают обычно системой стохастических матриц.
Используя такой способ задания вероятностных автоматов, можно ввести теоретико-множественные операции над ними по аналогии с опе- рациями над детерминированными автоматами, но ограничения на стоха- стические матрицы, которые при этом нужно накладывать, делают класс автоматов, к которым применимы эти операции, довольно узким. Поэто- му переходим сразу к алгебраическим операциям.
Зададим два вероятностных автомата
(
)
1
, ,
,
A
X Q q
Q
=
∈ P и
(
)
1
, ,
,
B
Y V v V
=
∈ S . Вероятностный автомат
(
)
1
, ,
,
C
Z W w W
=
∈
R будет являться произведением автоматов
А и В (С=А×В), если:
Z=X×Y; (2.4.42)
W=Q×V; (2.4.43)
R=P×S, (2.4.44) где
w
1
=(
q
1
,
v
1
). Формулы (2.4.42), (2.4.43) – это обычные декартовы про- изведения, а (2.4.44) – это декартово произведение, образуемое по прави- лу прямого произведения стохастических матриц из
P и S.
Пример 2.22.
Два вероятностных автомата
(
)
1
, ,
,
A
X Q q
Q
=
∈ P и
(
)
1
, ,
,
B
Y V v V
=
∈ S заданы своими стохастическими матрицами:

105 1
2 2 1 1 2 3 3 3 3
,
1 3
1 1 4 4 2 2
x
x












=
=












P
P
,
1 2
1 1 1 0 2 2
,
1 4 1 3 5 5 4 4
y
y








=
= 













S
S
Найдем автомат
C A B
= × . Входной алфавит Z и алфавит состоянийW автомата
С, согласно формулам (2.4.42), (2.4.43), будут равны
{
}
1 2
3 4
, , ,
Z
z z z z
=
,
{
}
1 2
3 4
,
,
,
W
w w w w
=
, где
(
)
1 1
1
,
z
x y
=
,
(
)
2 1
2
,
z
x y
=
,
(
)
3 2
1
,
z
x y
=
,
(
)
4 2
2
,
z
x y
=
,
(
)
1 1
1
,
w
q v
=
,
(
)
2 1
2
,
w
q v
=
,
(
)
3 2
1
,
w
q v
=
,
(
)
4 2
2
,
w
q v
=
Стохастические матрицы автомата
С найдем по формуле (2.4.44) пря- мым произведением (элемент на элемент) соответствующих матриц ав- томатов
А и В.
1 1
1 2
1 0
0 3
3 2 1 2
8 1
4 1 0 3 3 15 15 15 15 1 4 1
3 1
3 0
0 5 5 4 4 4
4 1
1 3
3 20 5
20 5
z
x
y




















=
×
=
×
= 




 
 


 
 











R
P
S
,
2 1
2 1
1 1
1 3
3 6
6 1
1 1
1 2 1 1 1 6
2 12 4
3 3 2 2 1 3 1
1 3
3 1
3 4 4 8
8 8
8 4 4 1
3 3
9 16 16 16 16
z
x
y







 
 


 
 



=
×
=
×
=

 


 
 



















R
P
S
,

106 3
2 1
1 2
0 0
3 3
1 2
1 4
2 8
1 0 3 3 15 15 15 15 1 4 1 1 1
1 0
0 5 5 2 2 2
2 1
2 1
2 10 5
10 5
z
x
y




















=
×
=
×
= 




 
 


 
 











R
P
S
,
4 2
2 1
1 1 1 6
6 3 3 1 2 1
1 1 1 1 1 3 3 12 4 6 2 2 2 1 3 1 1 1
1 1 1 4 4 2 2 4
4 4 4 1
3 1 3
8 8 8 8
z
x
y







 
 


 
 



=
×
=
×
=

 


 
 



















R
P
S
Вероятностный автомат
(
)
1
, ,
,
D
Z W w W
=
∈
R является суммой авто- матов
А и В (D=A+B), если:
Z=({1}×X)∪({2}×Y); (2.4.45)
W=Q×Y; (2.4.46)
R=(P×E
B
)∪(E
A
×S), (2.4.47) где
w
1
=(
q
1
,
v
1
), а Е
А
и Е
В
– единичные матрицы, имеющие порядок матриц из
P и S соответственно, причем произведения в круглых скобках выра- жения (2.4.47) являются прямыми произведениями. Попутно вспомним, что порядки стохастических матриц P и S (они, конечно, квадратные) равны соответствующим мощностям множеств
Q и V.
Если входные алфавиты вероятностных автоматов
А и В не пересека- ются
X∩Y=Ø, то формулу (2.4.45) можно заменить на:
Z=X∪Y. (2.4.48)
Пример 2.23.
Найдем сумму автоматов
А и В из примера 2.22.

107
Поскольку входные алфавиты автоматов
А и В не пересекаются, то для определения входного алфавита автомата
D=A+B пользуемся форму- лой (2.4.48):
{
}
1 2
1 2
, , ,
Z
x x y y
=
Далее по формуле (2.4.47) находим стохастические матрицы авто- мата
D.
1 1
2 1
0 0
3 3
2 1 2
1 0
0 1 0 3 3 3
3 0 1 1
3 1
3 0
0 4 4 4
4 1
3 0
0 4
4
x
x
B


















=
×
=
×
= 




 
 













R
P
E
,
2 2
1 2
0 0
3 3
1 2
1 2
0 0
1 0 3 3 3
3 0 1 1 1 1
1 0
0 2 2 2
2 1
1 0
0 2
2
x
x
B


















=
×
=
×
= 




 
 













R
P
E
,
1 1
1 0 0 0 1 4 1 0 0 0 1 0 5 5 1 4 0 1 0 0 1 0 5 5 1 4 0 0 5 5
y
A
y














=
×
=
×
=




















R
E
S
,

108 2
2 1 1 0 0 2 2 1 1 1 3 0 0 1 0 2 2 4 4 0 1 1
3 1 1 0 0 4 4 2 2 1
3 0 0 4 4
y
A
y







 


 



=
×
=
×
=

 










 








