Математическая теория систем. Математические основы теории систем
 Скачать 2.07 Mb.
|
|
Пример 2.13. Исходный граф автомата изображен на рис. 2.12,а. Пусть q 1 – начальное состояние, а q 2 – заключительное. Расщепляем вер- шину q 1 (рис. 2.12, б). Вычисляем переход от q 1 ' к q 1 '' (рис. 2.12, в). Со- t kk t pk t ks q p q k q s а) q p q s ( ) * ps pk kk ks t t t t ∪ ⋅ ⋅ б) Рис. 2.11.Удаление вершины с петлей 80 единяем q 1 ' и q 1 '' (рис. 2.12, г). Записываем окончательный результат (рис. 2.12, д). Теперь можно сформулировать графический алгоритм анализа аб- страктных автоматов. 1. По графу автомата находим исток и сток. Если их нет, то с началь- ной вершиной q i соединяется пустым ребром новая вершина q i ', а заклю- чительная вершина q j соединяется пустым ребром с новой вершиной q j '. После этого q i ' берется как исток, а q j ' – как сток. 2. Все параллельные пути приводятся к форме k s x x ∪ , а все последо- вательные – к форме x k ⋅x s 3. Получаем индексный остаток графа, отмечая вершины q i , q j и ин- дексные вершины. Находим приращения остаточных дуг. 4. Устраняем последовательно все индексные вершины индексного остатка графа. Приращение пути от вершины q i к вершине q j есть регу- лярное выражение события, представимого в автомате состоянием q j при условии, что q i – начальное состояние автомата. х 1 х 1 х 2 q 1 q 2 x 2 а) q 1 '' x 1 q 1 ' x 1 x 2 q 2 x 2 б) 2 2 1 x x x ∗ х 1 q 1 ' ' q 1 ' в) 1 2 2 1 x x x x ∗ ∪ х 2 q 1 x 2 q 2 г) ( ) 1 2 2 1 2 2 x x x x x x ∗ ∗ ∗ ∪ q 1 q 2 д) Рис. 2.12. Пример расщепления сложного контура обратной связи 81 Пример 2.14. Рассмотрим автомат, заданный своим графом переходов (см. рис. 2.13). Пусть начальное состояние автомата 1 q , а заключительное – 7 q . Тре- буется провести анализ автомата, т.е. найти регулярное выражение, пред- ставимое этим автоматом. Поскольку вершина 1 q является истоком, а вершина 7 q – стоком, вводить дополнительные вершины не требуется. В графе на рис. 2.13 две индексные вершины – 2 q и 4 q . Можно оставить любую из них, например, 4 q . Тогда индексный остаток графа будет та- ким, как на рис. 2.14. q 1 1 q q 2 q 3 q 4 q 5 q 6 q 7 x 1 x 2 x 3 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 4 Рис. 2.13. Граф автомата 82 Путь ( ) ( ) 3 5 6 7 8 9 13 11 12 x x x x x x x x x ∗ ∪ ∪ от вершины 4 q до вершины 7 q не является остаточным, так как проходит через индексную вершину 4 q . Устраняя индексную вершину 4 q , получаем окончательное выражение для регулярного события, представимого автоматом при условии, что начальное состояние автомата – 1 q , а заключительное – 7 q : 1 2 1 5 6 7 8 9 4 3 2 3 5 6 7 8 9 11 12 13 3 5 6 7 8 10 12 1 5 6 7 8 10 12 ( ( ) )( ( ) ) ( ( ) ) ( ) x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ∗ ∗ ∗ ∗ ∗ ∪ ∪ ∪ ∪ ∪ ∪ ∪ ∪ ∪ ∪ ∪ 2.4 Алгебра абстрактных автоматов Рассмотрим свойства теоретико-множественных и алгебраических опе- раций на множестве абстрактных автоматов. Есть две теоретико- множественные операции – объединение и пересечение, а также четыре алгебраические – умножение, суммирование, суперпозиция и композиция. Все эти операции бинарные и играют важную роль при синтезе автоматов, так как на структурном уровне они соответствуют различным способам соединения простых (в частности элементарных) автоматов между собой при построении структурных схем более сложных автоматов [9]. Множество автоматов совместно с операциями над ними образуют алгебру абстрактных автоматов, которую не нужно путать с алгеброй регулярных событий на множестве слов входного алфавита произвольно- го автомата. Задать определенную бинарную операцию на множестве автоматов означает указать закон, по которому любым двум автоматам из некоторо- го множества автоматов сопоставляется третий автомат из этого же мно- q 4 q 7 ( ) 11 12 13 3 5 6 7 8 10 12 x x x x x x x x x x ∗ ∪ ∪ ∪ q 1 1 5 6 7 8 10 12 ( ) x x x x x x x ∗ ∪ ( ) 4 3 2 3 5 6 7 8 9 x x x x x x x x x ∗ ∪ ∪ ∪ Рис. 2.14. Индексный остаток графа 1 2 1 5 6 7 8 9 ( ) x x x x x x x x ∗ ∪ ∪ 83 жества. Какое именно множество имеется в виду, зависит от конкретного случая (от конкретной операции), а равенство понимается, как правило, с точностью до изоморфизма. 2.4.1. Теоретико-множественные операции Операции объединения и пересечения автоматов играют вспомога- тельную роль при задании алгебраических операций, хотя их можно рас- сматривать и как самостоятельные операции на множестве В(L) подавто- матов произвольного непустого автомата L. Тогда объединение двух ав- томатов А ∈ В(L) и В ∈ В(L) представляет автомат С=А ∪ В, который являет- ся эквивалентным продолжением автоматов А и В, а пересечение пред- ставляет автомат D ∈ B(L), по отношению к которому автоматы А и В яв- ляются эквивалентными продолжениями. Зададим операции объединения и пересечения более конкретно. Пусть L – произвольный непустой автомат Мили, а В(L) – множество его подав- томатов. Пусть далее А ∈ В(L) и В ∈ В(L) – подавтоматы автомата L, при- чем и А, и В имеют одинаковые начальные состояния, совпадающие с начальным состоянием L. Пусть заданы автомат А=(Х 1 , Q 1 , Y 1 , q 1 ∈ Q 1 , F 1 ( x ∈ X 1 / y ∈ Y 1 )) и автомат В=(Х 2 , Q 2 , Y 2 , q 1 ∈ Q 2 , F 2 ( x ∈ X 2 / y ∈ Y 2 )). Тогда авто- мат С=(X,Q,Y,q ∈ Q,F(x ∈ X/y ∈ Y)) будет являться объединением А и В, если множества X, Y, Q и отображение F определяются по формулам X=( { 1 }× X 1 ) ∪ ( { 2 }× X 2 ); (2.4.1) Q=Q 1 ∪ Q 2 ; (2.4.2) Y=( { 1 }× Y 1 ) ∪ ( { 2 }× Y 2 ); (2.4.3) Fq=F 1 q ∪ F 2 q, (2.4.4) где q ∈ Q. Для тех состояний, когда q ∉ Q 1 , полагаем F 1 q=Ø, а при q ∉ Q 2 имеем F 2 q=Ø. Если не происходит нарушения автоматности для автомата С, то есть равенство F 1 q(x/y)=F 2 q(x/y) не нарушается для любых q ∈ Q, x ∈ X и y ∈ Y (когда оба отображения не пусты) или если X 1 ∩ X 2 =Ø; (2.4.5) Y 1 ∩ Y 2 =Ø, (2.4.6) 84 то формулы (2.4.1) и (2.4.3) упрощаются и принимают вид X=X 1 ∪ X 2 ; (2.4.7) Y=Y 1 ∪ Y 2 . (2.4.8) В том случае, когда А и В вполне определенные автоматы, автомат С=А ∪ В также вполне определен, в противном случае автомат С будет частичным. Пример 2.15. Автоматы заданы своими автоматными таблицами. A q\x x 1 x 2 1 - 3, y 2 2 2, y 2 - 3 3, y 1 2, y 3 B q\x x 1 x 2 x 3 1 2, y 1 3, y 2 - 2 2, y 2 - 1, y 1 3 - - 1, y 3 Найдем их объединение C A B = ∪ . Поскольку нарушения условий автоматности не происходит, то нет необходимости различать одинако- вые буквы алфавитов, и поэтому пользуемся формулами (2.4.7) и (2.4.8), а также формулами (2.4.2) и (2.4.4). В результате получаем автомат С: С q\x x 1 x 2 x 3 1 2, y 1 3, y 2 - 2 2, y 2 - 1, y 1 3 3, y 1 2, y 3 1, y 3 Операцию объединения с соответствующими формулами (2.4.1) – (2.4.8) легко объединить и на случай n автоматов. Из формул (2.4.2), (2.4.4), (2.4.5) – (2.4.8) следует, что каждый автомат Мили может быть представлен объединением автономных автоматов по входным и выходным буквам: ( ) ( ) x y x X y Y A A A ∈ ∈ = ∪ ∪ ∪ 82 Такое представление используется при разложении автоматов по раз- личным операциям. Автоматное отображение S C ( q 1 , x ), индуцируемое автоматом С, есть продолжение автоматных отображений S A ( q 1 , x ) на множество Х*. Пересечением автоматов А и В будет являться автомат D=A ∩ В, если его алфавиты X, Q, Y и отображение F определяется формулами X=X 1 ∩ X 2 ; (2.4.9) Q=Q 1 ∩ Q 2 ; (2.4.10) Y=Y 1 ∩ Y 2 ; (2.4.11) Fq=F 1 q ∩ F 2 q, (2.4.12) где q ∈ Q. Пример 2.16. Найдем пересечение автоматов А и В из примера 2.15. Применяя формулы (2.4.9) – (2.4.12), получаем автоматную таблицу автомата D A B = ∩ : D q\x x 1 x 2 1 - 3, y 2 2 2, y 2 - 3 - - Так же, как и операцию объединения, операцию пересечения, опреде- ляемую формулами (2.4.9) – (2.4.12), можно распространить на случай n автоматов. Задание объединения и пересечения автоматов Мура наталкивается на трудности, связанные с тем, что одинаковые состояния могут иметь раз- ные значения функции отметок, в связи с чем рекомендуется сначала ин- терпретировать автоматы Мура эквивалентными автоматами Мили, а за- тем находить их объединение или пересечение по известным формулам. Нетрудно заметить, что операции объединения и пересечения автома- тов ассоциативны, коммутативны и дистрибутивны. 2.4.2. Алгебраические операции К алгебраическим операциям над автоматами относятся умножение, суммирование, суперпозиция и композиция. 83 Операция умножения графов приводит к двум операциям умножения автоматов. Первая операция, обозначаемая × , применяется к произволь- ным автоматам с раздельными входами, то есть с разными входными ал- фавитами, а вторая обозначается ⊗ и применяется к автоматам с общим входом, то есть с одним и тем же входным алфавитом. Произведением произвольных непустых автоматов А=(X,Q,Y,q 1 ∈ Q , F(x ∈ X/y ∈ Y)) и B=(U,W,V,w 1 ∈ W,P(u ∈ U/v ∈ V)) будет назы- ваться автомат К=(Z,H,S,h 1 ∈ H,R(z ∈ Z/s ∈ S)), у которого Z=X × U; (2.4.13) H=Q × W; (2.4.14) S=Y × V; (2.4.15) Rh=Fq × Pw, (2.4.16) где q ∈ Q, w ∈ W, h ∈ H, h=(q,w), z=(x,u), s=(y,v). Начальным состоянием автомата К=А × В будет состояние h 1 =( q 1 , w 1 ) . Если оба автомата А и В вполне определенные, то и их произведение яв- ляется вполне определенным автоматом. Если хотя бы один из исходных автоматов частичный, то в результате умножения получаем частичный автомат. Можно определить операцию умножения и через матрицы соедине- ний. Пусть имеется матрица соединений автомата А: ( ) / A i j r x y = R , где i, j ∈{ 1, 2, … m } и ( ) / , если по букве с выходом , / 0, если ; i i j q i j j q x y q F x X y Y r x y q F ∈ ∈ ∈ = ∉ и матрица соединений автомата В: ( ) / B k l r u w = R , где k, l ∈{ 1, 2, … n } и ( ) / , если по букве с выходом , / 0, если ; k k l w k l l w u v w P u U v V r u v w P ∈ ∈ ∈ = ∉ 84 Матрица соединений R k автомата K=А×В равна прямому произведе- нию матриц R A и R B , то есть R K = R A × R B , а ее элементы определяются так: ( ) ( ) ( ) , / , , если / и / , / 0, если 0 или 0, i j k l i j k l x u y v r x y r u v r z s r r αβ = = = = = где α,β∈{1, 2, … p}, p=m·n, z=(x,u), s=(y,v). Пример 2.17. Автоматы А и В заданы автоматными таблицами: A q\x x 1 x 2 q 1 q 2 , y 1 q 1 , y 2 q 2 q 3 , y 2 - q 3 - q 3 , y 1 B w\u w 1 w 1 , v 2 - w 2 w 1 , v 1 w 2 , v 1 Найдем произведение этих автоматов, т.е. автомат K A B = × . Входной алфавит автомата K – это упорядоченные пары входных букв автоматов А и В: обозначим их { } 1 2 3 4 , , , , Z z z z z = где ( ) 1 1 1 , z x u = , ( ) 2 1 2 , z x u = , ( ) 3 2 1 , z x u = , ( ) 4 2 2 , z x u = Выходной алфавит автомата K обозначим через { } 1 2 3 4 S= s , , , s s s , где ( ) 1 1 1 , s y v = , ( ) 2 1 2 , s y v = , ( ) 3 2 1 , s y v = , ( ) 4 2 2 , s y v = Алфавит состояний автомата K – это { } 1 2 3 4 5 6 , , , , , H h h h h h h = , где ( ) 1 1 1 , h q u = , ( ) 2 1 2 , h q u = , ( ) 3 2 1 , h q u = , ( ) 4 2 2 , h q u = , ( ) 5 3 1 , h q u = , ( ) 6 3 2 , h q u = Найдем отображение 1 Rh по входной букве 1 z . Состояние 1 h – это пара ( ) 1 1 , q w , а входная буква 1 z – это пара ( ) 1 1 , x u . Автомат А из со- стояния 1 q по входной букве 1 x согласно автоматной таблице перейдет в состояние 2 q , а автомат В из состояния 1 w по входной букве 1 u перейдет в состояние 1 w . Эта пара ( ) 2 1 , q w согласно обозначениям есть состояние 85 3 h автомата K. На выходах автоматов А и В появятся при этом буквы 1 y и 2 v соответственно. Пара ( ) 1 2 , y v – это буква 2 s выходного алфавита автомата K. Аналогично находим отображение 1 Rh по входной букве 3 z . Отображение состояния 1 w автомата В по входной букве 2 u не опреде- лено, поэтому также не определено отображение состояния 1 h автомата K по входным буквам 2 4 и z z . Таким образом, получаем { } 1 3 1 2 1 3 4 ( , ), ( , ) Rh h z s h z s = Далее проделываем то же самое для состояний 2 3 4 5 6 , , , , h h h h h . Соот- ветствующие отображения этих состояний имеют вид { } { } { } { } { } 2 3 1 1 4 2 1 1 3 3 2 4 3 3 5 1 4 4 5 1 3 6 2 3 5 5 3 2 6 5 3 1 6 4 1 ( , ), ( , ), ( , ), ( , ) ; ( , ) ; ( , ), ( , ) ; ( , ) ; ( , ), ( , ) . Rh h z s h z s h z s h z s Rh h z s Rh h z s h z s Rh h z s Rh h z s h z s = = = = = По полученным отображениям можно составить автоматную таблицу: K h\z 1 z 2 z 3 z 4 z 1 h 3 2 , h s |