Математическая теория систем. Математические основы теории систем
 Скачать 2.07 Mb.
|
|
R R R R R ∪ , где R A(t/l) – матрица соединений автономного подавтомата A t/l и буква t∈T, по которой выделен этот подавтомат, исключена из матрицы; R B(l/t) – мат- рица соединений автономного подавтомата B l/t , а буква l∈L исключена. В более общем случае автоматы А и В могут иметь и общий входной алфавит N: A=(N, X, V, L, v 1 ∈V, F(n∈N, x∈X, t∈T/l∈L)), B=(N,Y,W,T, w 1 ∈W, P(n∈N, y∈N, l∈L/t∈T)). Тогда композиция А и В определяется вы- ражением ( ) n n n N C A B A B ∈ = = ∪ , где A n и B n – автономные автоматы по буквам входного алфавита n∈N. Учитывая (4.4.36) получим ( / ) ( / ) ( ( )) n t l n l t n N t T l L C A B ∈ ∈ ∈ = × ∪ ∪ , то есть автомат C задан выражениями 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 , |