Математическая теория систем. Математические основы теории систем
 Скачать 2.07 Mb.
|
|
x ∈Х* и u ∈U* – слова, отличающиеся длиной не более чем на одну букву: 1 2 k i i i x x x = x , 1 2 1 k j j j u u u − = u Слово z ∈Z* называется сплетением слов х и u , обозначается z = x 〉〈 u и образуется чередованием букв х и u : 1 1 2 2 1 k k i j i j j j x u x u u x − = 〉〈 = z x u Любые две соседние буквы слова z принадлежат разным входным ал- фавитам. Если областью определения частичного отображения S A служит мно- жество допустимых слов х ∈Х*, а областью определения отображения S B – множество допустимых слов u ∈U*, то областью частичного отображе- А В Х U Y V эквивалентно М Z S 94 ния S M будет множество слов z ∈Z*, полученных сплетением пар допу- стимых слов х и u , отличающихся длиной не более чем на одну букву. Следовательно, можно записать S M ( z )= S M ( x 〉〈 u )= S A ( x ) 〉〈S B ( u )= y 〉〈 v = s , где y ∈Y*, v ∈V*, s ∈S*. Отображение S M называется сплетением отображений S A и S B и обо- значается M A B S S S = 〉〈 . Для произвольных автоматов А, В, и С выполняются следующие соот- ношения: ( А×В)×С=А×(В×С), A B B A × × ∼ , (2.4.26) A E E A A × × ∼ ∼ , где роль единичного автомата Е играет автомат Е=(Х,Q,Y,q∈Q,F(x∈X/y∈Y)), причем X={x}, Y={y}, Q={q}, а Fq={q(x/y)}. Поэтому множество произвольных автоматов совместно с операцией умножения ×образует коммутативный моноид 1 с единичным элементом Е. Обозначим это множество через В × . Если брать множество автоматов с одним и тем же входным алфави- том, то очевидно, что для любых автоматов А, В, и С из этого множества выполняются соотношения, аналогичные (4.4.26), и, следовательно, это множество по операции ⊗ образует коммутативный моноид с единичным элементом Е=(X,Q,Y,q∈Q,F(X∈X/y∈Y)), где X={x 1 , x 2 , … x p } – входной алфавит автоматов этого множества, Q={q}, Y={y}, Fq={q(x 1 ∪x 2 ∪…∪x p / y)}. Это будет множество В ⊗ Аналогично множество произвольных автоматов по операции сумми- рования образуют коммутативную полугруппу (несущее множество В + ). Следующая алгебраическая операция – суперпозиция двух автоматов. Возьмем два произвольных автомата из множества автоматов Мили, вхо- дящие и выходящие алфавиты которых могут пересекаться: А=(X 1 , Q,Y 1 , 1 Моноидом в общей алгебре называют полугруппу с единицей Е. Полугруппа, в свою оче- редь, – это множество элементов с заданной на этом множестве бинарной ассоциативной операцией, обычно называемой умножением. Таким образом, для любого элемента А моно- ида выполняется соотношение Е·А=А·Е=А. 95 q 1 ∈Q, F(x∈X/y∈Y 1 )) и B=(X 2 , W,Y 2 , w 1 ∈W, P(x∈X 2 / y∈Y 2 )), где пересечение Y 1 ∩X 2 = Z не пусто в общем случае. Отображение произвольного состояния q∈Q автомата А можно пред- ставить в следующем виде: 1 2 1 p y y y y y Y Fq F q F q F q F q ∈ = ∪ ∪ ∪ = ∪ , где p – число букв входного алфавита Y 1 , а F y q – отображение состояния q, при котором на выходе появляется буква y∈Y 1 . Отображение произвольного состояния w автомата В представим в виде 1 2 2 s x k x x x x X Pw P w P w P w P w ∈ = ∪ ∪ ∪ = ∪ , где s – число букв входного алфавита Х 2 , а P x w – отображение состояния w по букве х∈Х 2 Автомат N=(X 1 , H,Y 2 , h 1 ∈H, S(x∈X 1 / y∈Y 2 )) будет являться суперпози- цией автоматов А и В (N=A∗B), если множество состояний H=Q×W, (2.4.27) а отображение S задано выражением 1 1 2 2 1 ( ) ( ) ... ( ) ( ) m m z z z z z z z z z Z Sh F q P w F q P w F q P w F q P w ∈ = × ∪ × ∪ ∪ × = × ∪ , где h∈H, q∈Q, w∈W, h=(q, w), z∈Z=Y 1 ∩X 2 ( m – число букв алфавита Z). Пример 2.20. Даны два автомата А и В: А x 1 x 2 q 1 2 1 , q y 3 2 , q y q 2 3 2 , q y - q 2 - 2 1 , q y В y 1 y 2 w 1 2 2 , w v - w 2 2 1 , w v 1 1 , w v 95 Найдем суперпозицию N A B = ∗ . Входной алфавит автомата N сов- падает со входным алфавитом автомата А: { } 1 2 , X x x = , а выходной алфа- вит – с выходным алфавитом автомата В: { } 1 2 , V v v = . Алфавит состоя- ний, как и во всех алгебраических операциях, – это { } 1 2 3 4 5 6 , , , , , H h h h h h h = , где ( ) 1 1 1 , h q w = , ( ) 2 1 2 , h q w = , ( ) 3 2 1 , h q w = , ( ) 4 2 2 , h q w = , ( ) 5 3 1 , h q w = , ( ) 6 3 2 , h q w = Возьмем состояние h 1 автомата N. Оно соответствует состоянию q 1 автомата А и состоянию w 1 автомата В. По входной букве x 1 автомат А перейдет из состояния q 1 в состояние q 2 с выходом y 1 , и по этой же букве y 1 автомат В перейдет из состояния w 1 в состояние w 2 с выходом v 2 . По- этому пара ( q 2 , w 2 ) есть значение функции перехода автомата N: ( ) ( ) 1 1 2 2 4 , , N h x q w h = = δ , а v 2 есть значение функции выхода автомата N: ( ) 1 1 2 , N h x v = λ . По входной букве x 2 автомат А переходит из состояния q 1 в состояние q 3 с выходом y 2 , но отображение состояния w 1 автомата В по этой букве ( y 2 ) не определено, поэтому не определено и отображение со- стояния h 1 автомата N по входной букве x 2 . Таким образом, получаем ( ) { } 1 4 1 2 , Sh h x v = Рассуждая аналогичным образом, получим отображения остальных состояний: ( ) ( ) { } 2 4 1 1 5 2 1 , , , Sh h x v h x v = , 3 Sh = ∅ , ( ) { } 4 5 1 1 , Sh h x v = , ( ) { } 5 4 2 2 , Sh h x v = , ( ) { } 6 4 2 1 , Sh h x v = Автоматная таблица, составленная по этим отображениям, приведена ниже: x 1 x 2 h 1 h 4 , v 2 - h 2 h 4 , v 1 h 5 , v 1 h 3 - - h 4 h 5 , v 1 - h 5 - h 4 , v 2 h 6 - h 4 , v 1 96 Суперпозицию автоматов можно представить и через разложение ис- ходных автоматов на автономные. Представим автомат А объединением автономных автоматов по выходной букве: 1 y y Y A A ∈ = ∪ , а автомат В объединением автономных автоматов по входной букве: 2 x x X B B ∈ = ∪ Тогда автомат N=A∗B будет задан выражением 1 1 2 2 1 ( ) ( ) ... ( ) ( ) n n z z z z z z z z z Z N A B A B A B A B ∈ = × ∪ × ∪ ∪ × = × ∪ , (2.4.29) где Z=Y 1 ∩X 2 . Из последнего выражения следует, что операция суперпозиции авто- матов соответствует композиции соответствующих отображений, если Y 1 = X 2 , т. е. S N ( x )=S B ( y )=S B (S A ( x )), или N A B S S S = , где х ∈Х 1 , y ∈Y 1 . Если же Y 1 ≠X 2 и Y 1 ∩X 2 = Z, то получим композицию сужений отобра- жений S A и S B на множество Z. Операция суперпозиции автоматов ассо- циативна, но, конечно же, некоммутативна, так же как и композиция отображений. Поэтому множество автоматов по операции суперпозиции образует некоммутативную полугруппу В ∗ . Теперь запишем операцию суперпозиции в матричной форме. Разложим матрицу соединений R A автомата А по автономным матри- цам выходного алфавита: 1 A Ay y Y ∈ = R R ∪ , и из каждой автономной матрицы исключим ту букву, по которой выде- лена эта матрица. 97 Матрицу автомата В представим объединением матриц автономных автоматов входного алфавита: 2 B Bx x X ∈ = R R ∪ , также исключая из каждой автономной матрицы ту букву, по которой данная матрица выделена. Тогда матрица соединений R N автомата N=А∗В при условии, что Y 1 ∩X 2 = Z≠Ø, определиться формулой ( ) z z N A B z Z ∈ = × R R R ∪ Введем понятие единичного и обратного автоматов на множестве произвольных автоматов. Под единичным автоматом Е понимается такой автомат, который любое слово входного алфавита преобразует в такое же входное слово. Такой автомат индуцирует тождественное отображение на множестве слов Х* алфавита Х. Ясно, что это автомат с единственным состоянием, матрица соединений которого имеет вид 1 1 2 2 / / / E n n x x x x x x = ∪ ∪ ∪ R . Из определения единичного автомата Е следует, что такой автомат является правой и левой единицей в полугруппе В ∗ A E E A A ∗ ∗ ∼ ∼ Обратным автоматом 1 A − к автомату А, индуцирующему отображе- ние S A ( x) множество слов x∈Х* на множество выходных слов y∈Y*, называется такой автомат, который индуцирует обратное отображение ( ) 1 A S − y . Очевидно, что обратный автомат существует только тогда, когда отображение S A является биективным (взаимно-однозначным) отображе- нием. В этом случае в любой строке его матрицы соединений не может быть двух пар “вход-выход”, имеющих одинаковые выходные буквы. Поэтому для построения матрицы соединений обратного автомата доста- точно в матрице соединений автомата А в каждой паре “вход-выход” по- менять местами элементы этой пары. 98 Таким образом, подмножество автоматов D ∗ ⊂B ∗ , индуцирующих вза- имно-однозначное отображение, по операции суперпозиции образует некоммутативную группу 1 D ∗ . Операции суперпозиции двух автоматов соответствует последова- тельная их работа (рис. 2.18). Рис. 2.18. Суперпозиция двух автоматов Наиболее общий случай совместной работы автоматов задается опе- рацией композиции, а различные типы их соединений и виды работы, которые соответствуют введенным ранее операциям, являются частными случаями композиции автоматов. Зададим произвольные автоматы A=(X,V,L, v 1 ∈V, F(x∈X, t∈T/l∈L)) и B=(Y,W,T, w 1 ∈W, P(y∈Y,l∈L/t∈T)). Входной алфавит автомата А – это Х, V – алфавит состояний, L – выходной алфавит, F – отображение множества состояний V в себя по буквам входного алфавита х∈Х и выходного алфа- вита t∈T автомата В, при котором на выходе автомата А появляется вы- ходная буква l∈L. Аналогично для автомата В. Представим отображение F и P в виде объединения соответствующих выражений по буквам алфавитов T и L: / t l t T l L Fv F v ∈ ∈ = ∪ ∪ , / l t l L t T Pw P w ∈ ∈ = ∪ ∪ 1 Группой в общей алгебре называется полугруппа с единицей (моноид), для каждого эле- мента А которой существует обратный элемент 1 A − , так, что 1 A − · А=Е. А В Х 1 Х 2 Y 1 Y 2 эквивалентно N X 1 Y 2 99 Автомат C=(Z,Q,M, q 1 ∈Q, K(z∈Z/m∈M)) будет называться композици- ей автоматов А и В ( ) C A B = , если Z=X×Y; (2.4.30) Q=V×W; (2.4.31) M=L×T;(2.4.32) / / ( ) t l l t l L t T Kq F v P w ∈ ∈ = × ∪ , (2.4.33) где q=(v,w), q∈Q, v∈V, w∈W,а F t/l v – отображение состояния v по букве t∈T, при котором на выходе появляется буква l∈L, P l/t w – отображение состояния w по букве l∈L, при котором на выходе появляется буква t∈T. Композиции автоматов эквивалентна совместная работа автоматов, приведенная на рис. 2.19. Рис. 2.19. Композиция двух автоматов Автомат А можно разложить на автономные автоматы по входным буквам t∈T: t t T A A ∈ = ∪ , а каждый автономный автомат А t ,, свою очередь, – по буквам l∈L: / t t l l L A A ∈ = ∪ Таким образом: / t l t T l L A A ∈ ∈ = ∪ . (2.4.34) Аналогично и автомат В: А В Х Y L T эквивалентно С Z M 100 / l t t T l L B B ∈ ∈ = ∪ . (2.4.35) Из формул (2.4.30) – (2.4.35) следует, что автомат С A B = можно найти по формулам / / t l l t t T l L C A B ∈ ∈ = × ∪ . (2.4.36) Из последнего выражения легко получить операцию композиции в матричной форме. Возьмем матрицу соединений автомата А с элемента- ми: ( ) { } / , если по буквам , с выходом , / 0, если , , 1, 2,... , v v x l v F x X t T l L r xt l v F k α α β α β β ∈ ∈ ∈ ∈ = ∉ α β = где k – число состояний автомата А, и матрицу соединений автомата В: ( ) { } / , если по буквам , с выходом , / 0, если , , 1, 2,... , w w yl t w P y Y l L t T r yl t w P n γ γ δ γ δ δ ∈ ∈ ∈ ∈ = ∉ γ δ = где n – число состояний автомата В. Тогда матрица соединений автомата С A B = будет равна: ( / ) ( / ) c A B A t l B l t t T l L ∈ ∈ = = × |