ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.06.2024
Просмотров: 131
Скачиваний: 0
|
|
|
|
|
|
|
|
|
n-l |
„_i |
|
|
|
||
рассмотрение два |
отображения |
/ : |
X Г,- |
X Г4 и |
/ ' : Г 0 |
х Т „ - |
|||||||||
|
|
|
|
|
|
|
|
|
|
(=1 |
i=! |
|
|
|
|
Г„ х |
Гп , |
которые определим |
формулами |
|
|
|
|
|
|||||||
/(/Сг„ |
••• . /Сг„_,) |
(/<г„ |
-. • , |
Кг„_,), если V |
Кг, |
Ф |
0 , |
||||||||
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
(Кг, |
|
|
Кг„_,) |
в п Р о т и в н |
° м |
случае, |
|||
где |
(Кт,, |
• |
/Сг„_,)—такой кортеж, что |
п-1 |
Л г , # 0 > ' |
|
|||||||||
Г) |
|
||||||||||||||
|
|
|
|
|
|
((Кг„, Кг), |
|
если Кг„ П Кг |
Ф |
0 . |
|
||||
|
|
|
|
г„> |
гп ; |
| |
|
^ |
^ в |
П р О Т И |
В Н О М случае, |
|
|
||
где Кг |
такой класс разбиения |
Г,„ что ЛГг„ П Kvn |
ф |
0- |
|
|
|||||||||
|
Пусть |
(Кг,, |
|
Кгп) |
Є V |
произвольно, |
(ЛГг,, |
|
Кгп _,) = |
||||||
= |
f(Kr„ |
|
|
.... /Сг„_,), |
Кг. = j n V r , |
и (*г., /С'гя) = |
Г |
(Яг,, /Сг„)- |
|||||||
Введем в рассмотрение отображение \ : V ->- V", определяя |
его со |
||||||||||||||
отношением £ (/<"г„ |
АГгп) = |
(Кг,, |
/Сгп ). Функции |
переходов |
|||||||||||
компонент доопределяем согласно |
выражению |
|
|
|
|
||||||||||
|
|
|
8,.(/Сг., К г „ |
|
Я г , _ Р |
/ < г і + 1 , |
/Сгп _„ |
х) |
= |
|
|||||
|
|
|
— °i(Krt, |
Кг,, |
••• |
, Кг,_], |
Кг,+ 1 > |
••• . Кгп_г |
|
х), |
|
||||
где t = 1, 2, я. Тогда функция переходов Л автоматадоопределится согласно формуле
|
Л((Кг„ |
Кгп), |
*) = A (S (Л:г „ . . . . |
Кгп), |
х), |
|
|
||||
откуда |
следует, что |
для |
произвольных |
s £ V и х |
£ X |
A (s, |
х) |
£ |
|||
£ a (S), |
т. е. сеть |
связна |
относительно |
А. |
|
|
|
|
|
||
Определим семейство |
разбиений {Г[} (1 < ; і •< п) множества |
V, |
|||||||||
задавая |
Г; соотношением |
s = t (Г|) <-> рг, (s) = |
рг< (і). |
Из опреде |
|||||||
лений а и Г і следует |
|
|
|
|
|
|
|
|
|||
|
а = |
Ь (Г,) |
а (а) == а (Ь) (Г•) для всех |
a,b£S. |
|
(5.8) |
|||||
Пусть Го — П |
I V На основании определений Г0 , |
Г0 и (5.8) |
полу- |
||||||||
чаем |
|
b (Г0 ) «-» а (а) == а (&) (Го) для всех |
а, & £ S . |
(5.9) |
|||||||
|
а = |
||||||||||
Доопределим функцию выходов А автомата £6 так, чтобы выпол |
|||||||||||
нялось |
неравенство |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Г о > П л . |
|
|
|
|
(5.Ю) |
|
В общем случае для соответствующего доопределения функции Л может понадобиться увеличение выходного алфавита Y сети £f, т. е.
ПО
необходимо получить такую новую сеть Ж, которая бы отличалась от сети только выходным алфавитом и в автомате Ж = {У, X, У ь Л, Л) можно было бы так доопределить функцию Л, чтобы выполнялось нер авенство (5.10).
Предположим, |
что |
\Х\ = |
т. Пусть х — произвольное взаимно |
|||||
однозначное отображение к : X-у |
{1, 2, |
т]. Рассмотрим |
ото |
|||||
бражение со : S —>- Y"1, |
определяемое |
соотношением |
|
|
||||
со (а) = (X (а, |
и - 1 |
(1)), |
% (а, |
х - ' |
(2)), |
.. . , X (а, х " 1 (т))), |
|
|
|
|
|
|
|
|
I |
п-1 |
|
где и-1 —обращение отображения х. Пусть U = \s£V |
(~) p r ^ s ) ^ |
|||||||
ф 0^. Если множество |
U' = |
V— |
U не пусто, то определяем |
раз |
||||
биение 9 этого множества |
|
|
|
|
|
|
||
s = t (б) |
рг,- (s) = pr, (t) для |
всех |
г' (1 - < і •< II |
— 1). |
|
|||
Из определения разбиений 0 и Го следует справедливость имплика ции
|
|
|
s^t(Q)-+s^t(T0). |
|
|
|
( 5 П ) . |
||
Выбираем выходной алфавит У^ети Ж так, чтобы У s |
Уі и | 91 •< |
||||||||
<; | Y? |
— |
со (S) |. Введем в рассмотрение произвольное взаимно од |
|||||||
нозначное |
отображение |
у |
: 0 - > (У{" — со (5)). Функцию Л доопре |
||||||
деляем |
согласно соотношению |
(£ (s)), х), |
если |
s £ |
|
|
|||
|
|
Л (s, х) - |
Х(аг1 |
U, |
(5.12) |
||||
|
|
( |
^ |
( т ( / С е т |
е с д и |
s ^ |
^ |
||
Покажем, что при таком доопределении функции Л будет выполнять
ся неравенство (5.10). Пусть |
s = |
t (Щ). Согласно (5.2) для |
произ |
||||||||||||||||||||
вольного |
х |
£ X |
Л (s, х) = |
Л (t, |
х). |
Рассмотрим |
два случая. |
|
|
||||||||||||||
|
1. |
s £ |
U. |
|
Покажем, |
что |
t |
£ |
U. |
|
Допустим, |
что |
t (£ |
U. |
|||||||||
Пусть ys |
= |
(Л (s, х - ' (1)), |
|
|
Л (s, х - ' |
(т))) и & |
= (Л (*, х - ' |
(1)), ... |
|||||||||||||||
|
Л (t, |
%~х (т))). Тогда, поскольку |
s = |
|
f (ПЛ ), то г/5 |
= г/,. На ос |
|||||||||||||||||
новании |
(5.12) |
можно утверждать, |
что |
|
ys |
£ |
со (5), |
и |
поэтому yt |
£ |
|||||||||||||
£ |
со (S). С другой стороны, |
так |
как |
t |
|
$ |
(7, |
то yt |
— у |
(Кв |
(t)) |
и |
|||||||||||
yt |
$ |
со (5), что приводит |
нас к |
противоречию. |
|
|
|
|
|
|
|
||||||||||||
|
Поскольку |
t |
£ U, то на основании (5. 12) можно утверждать, что |
||||||||||||||||||||
для |
произвольного х£ |
X |
X ( а - ' ( | (s)), |
х) = X (а~1 |
(£(0), |
|
и |
||||||||||||||||
а - 1 |
(§ |
= а-'(|(ґ))-(Щ). |
В |
силу |
неравенства |
Г0 > |
Па. получаем |
||||||||||||||||
|
(£ (s )) = |
a - 1 |
(£ (*)) (Г0 ) |
и, учитывая |
|
(5.9), |
приходим |
к |
соотно |
||||||||||||||
шению | (s) = |
I |
(t) (Г0 ). Из |
определения |
отображения |
g |
следует,, |
|||||||||||||||||
что для |
произвольного |
и £ |
(У |
и s= £ (w) (Г0 ). |
Поэтому |
s = |
t (Г0) |
||||||||||||||||
и неравенство |
(5.10) доказано. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
2. |
sffc U. Аналогично |
предыдущему |
случаю легко показать, что |
|||||||||||||||||||
/ $ U. Тогда из (5.12) получаем, что для всех х£ |
X ргх |
<*) (7 (Кв (s))) = |
|||||||||||||||||||||
= |
Ргк (*) (У (/Се (()))> а это |
равносильно |
у (/Се (s)) = |
7 |
(/Се (*)•)• У ч и " ' |
||||||||||||||||||
тывая взаимную однозначность отображения у, |
получаем |
Ко (s) |
= |
|||
— Ко (t), |
т. е. s == t (6). Из (5.11) следует s = t (Го). Таким образом, |
|||||
и в этом случае неравенство (5.10) справедливо. |
|
|
|
|||
Поскольку построенная сеть Ж, реализующая сильно |
связный |
|||||
автомат |
Л, связна |
относительно А, |
множество |
ее компонент Л |
= |
|
= {At} |
(1 < і < |
п — 1) замкнуто |
и ф (гр (А)) |
= Го > Щ , то |
на |
|
основании следствия 5.1 можно утверждать, что сеть §t компонентнодиагностируема. Теорема 5.3 до казана.
Доказательство теоремы 5.3 кон структивно и является методом по
дстроения компонентно-диагности руемой сети, реализующей" сильно связный автомат, который удов летворяет условиям теоремы 5.3.
Рис. |
14. |
Соединения компонент |
Проиллюстрируем |
этот |
метод на |
|||||||||||||
примере построения |
компонентно- |
|||||||||||||||||
сети |
Ut 1. |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
диагностируемой |
сети, |
реализую |
||||||||||
щей |
поведение состояний |
|
сильно |
связного |
|
автомата |
Л1, функции |
|||||||||||
переходов и выходов которого заданы |
|
табл. 15. |
|
|
|
|||||||||||||
Легко |
видеть, что |
= {1,2; |
3, |
6; |
4, |
5; |
7, |
8}, |
|
|
|
|||||||
л разбиения |
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
^ = { 1 , 2 , 3 , |
4, 5, |
6; 7, 8), |
|
|
|
|||||||||||
|
|
Г2 = |
{Т~2; 3, 4, 5, 6, 7, |
|
8}, |
|
|
|
||||||||||
|
|
Г3 |
= |
1, 3, 7; 2, 4, 8; 5; |
6} |
|
|
|
||||||||||
•таковы, что YXY«Y3 = |
О, Г0 |
= |
Г ^ |
= |
|
{1, 2; |
|
3, 4, |
5, 6; 7, 8} имеет |
|||||||||
свойство |
подстановки |
и Г, |
> |
Щ. |
Поэтому |
|
на основании теоремы |
|||||||||||
5.3 можно утверждать, что существует компонентно-диагностируе мая сеть j f f l , состоящая из трех компонент и реализующая поведе ние состояний автомата Л1. Соединения компонент сети Ж 1 показа ны на рис. 14. Введем следующие обозначения:
1, 2, 3, 4, 5. |
6; Ьл = 7, |
8; |
|
|
|||
а, = 1,2; |
Ь2 |
= |
3, 4, 5, б, 7, 8; |
|
|
||
: 1,2; |
Ь№ |
= |
3, 4, 5, |
6; |
с0 = |
7, 8; |
|
( а г , и 2 , а 3 ) ; |
В = (av |
а 2 , bs); С = (av |
о 2 , с 3 ) ; |
||||
( а „ а 2 |
, d3)\ Е = (av |
b2, as); |
F = (а1г |
Ьг, b3); |
|||
( а „ b2, с 3 ) ; Н = (alt |
b2, d3); |
К = (bv |
а 2 , а 3 ) ; |
||||
: ( b x , а 2 |
, Ь 3 ); |
М = ( b x , а 2 , с 3 ) ; |
Л/ = (& х , аг, d3); |
||||
і 12
|
|
О = [bv |
b,, |
a3); |
|
P = |
(bv |
b2, |
b3); |
|
R = (blt |
b2, |
c3 ); |
|
|
|||||
|
|
T = (bv |
b2, d3). |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Для доопределения |
|
функций |
переходов |
компонент |
Alt |
Ла , |
А3 |
и |
||||||||||||
автомата Ж 1 определим отображения f, f |
и £, |
задав |
их |
табл. 16, |
||||||||||||||||
17 и |
18 соответственно. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
Т а б л и ц а 15 |
|
|
Т а б л и ц а 16 |
|
|
|
||||||||
|
|
|
|
|
|
1 |
|
О |
|
1 |
|
|
(«1. |
а2 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
fa. |
|
|
|
|
||
|
|
1 |
3 |
|
7 |
|
0 |
|
0 |
|
|
(«1. |
ад |
|
(ах. |
|
|
|
||
|
|
2 |
4 |
|
8 |
|
0 |
|
0 |
|
|
|
а2) |
|
|
ад |
|
|
|
|
|
|
|
|
|
|
|
|
&*) |
|
(Ьг, |
|
|
|
|||||||
|
|
3 |
1 |
|
6 |
• 0 |
|
1 |
|
|
(Ьг, |
|
|
|
|
|||||
|
|
4 |
2 |
|
5 |
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
2 |
|
4 |
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
1 |
|
3 |
|
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
4 |
|
4 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
3 |
|
3 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а 17 |
|
|
|
|
Т а б л и ц а 18 |
|
|||||||
|
(ав. |
о3 ) |
(о0 . |
ад |
|
00. |
ад |
(ад |
ад |
|
|
л |
|
А |
|
К |
0 |
|
||
|
(а0. ад |
(ад |
ад |
(ад |
d3) |
(ад |
«У |
|
|
5 |
|
В |
|
L |
Р |
|
||||
|
(а0, |
ад |
(ад |
ад |
(с0 . |
a3) |
(с0 , |
|
|
|
С |
|
В |
|
М |
Р |
|
|||
|
ад |
|
|
D |
|
В |
|
N |
Р |
|
||||||||||
|
к . |
«"а) |
(ад |
ад |
(с0 . |
ад |
(ад |
|
|
|
|
|
||||||||
|
Ро. "а) |
(ад |
аз) |
|
(с0 . |
ад |
(ад |
ад |
|
|
Е |
|
Е |
|
0 |
0 |
|
|||
|
|
|
|
F |
|
F |
|
Р |
Р |
|
||||||||||
|
00. |
ад |
(ад |
ад |
(с0 . |
|
(ад |
ад |
|
|
|
|
|
|||||||
|
|
|
|
G |
|
G |
|
R |
Р |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Н |
|
Н |
|
Т |
Р |
|
|
|
|
|
|
Т а б л и ц а 19 |
|
|
|
|
|
|
|
Т а б л и ц а 20 |
||||||||
(а,. |
0) |
(а* 1) |
(6г , 0) |
(Ь2, 1) |
|
(а,. |
0) |
к |
і) |
|
(ад |
0) |
(ад |
і) |
||||||
°i |
al |
|
Ьг |
|
|
<h |
|
Пі |
|
аг |
|
Ьг |
|
Ьг |
|
Ьг |
|
Ьг |
|
|
a \ |
|
ai |
|
|
<h |
|
"і |
|
Ьг |
|
а2 |
|
Ьг |
|
Ьг |
|
Ьг |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а |
21 |
|
|||
|
(alt |
а2 , 0) (Оц, а2 > |
1) (а і , |
62 , 0) (а„ Ьъ |
1) (bv |
а„, 0) (6г , а„. 1) (ад 62 , 0) фг, |
Ь2,1) |
|||||||||||||
Аз |
аз |
|
а3 |
|
|
а3 |
|
d3 |
|
ь3 |
|
|
ь3 |
|
ь3 |
ь3 |
|
|||
bs |
b3 |
ь3 |
• |
h |
|
с3 |
|
ч3 |
|
|
а з |
|
а3 |
а3 |
|
|||||
|
|
ь3 |
ь3 |
ь3 |
|
ьа |
|
а3 |
|
|
а3 |
|
а3 |
а3 |
|
|||||
d3 |
ь3 |
ь3 |
|
|
а3 |
|
а3 |
|
аз |
|
|
а3 |
|
а3 |
а3 |
|
||||
Компоненты Лх , Лг , Л 3 |
сети j ^ l с |
доопределенными функциями |
пе |
|||||||||||||||||
реходов представлены табл. 19, 20, 21 соответственно. |
|
|
|
|
||||||||||||||||
В рассматриваемом примере |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
U |
= |
(Л, В, С, D, Е, |
F, G, Н, |
О, Р, R, |
Т), |
|
|
|
|
|
|
||||||||
|
V |
= |
{К, L , |
М, |
N), |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
8 2 - 1 6 3 6 |
113 |
Т а б л и ц а 22
А |
Е |
О |
0 |
0 |
В |
Е |
Р |
0 |
0 |
С |
Р |
Р |
0 |
0 |
D |
F |
Р |
0 |
0 |
Е |
А |
Н |
0 |
1 |
F |
В |
G |
1 |
0 |
G |
В |
F |
1 |
0 |
Н |
А |
Е |
0 |
1 |
К |
F |
F |
0 |
2 |
L |
Е |
Е |
0 |
2 |
М |
Е |
Е |
0 |
2 |
N |
Е |
Е |
0 |
2 |
О |
Е |
F |
1 |
1 |
Р |
Е |
Е |
1 |
1 |
R |
Е |
Е |
1 |
1 |
Т |
Е |
Е |
1 |
1 |
co(S) |
= |
{(0, |
0), (0, |
1), (1, 0), (1, 1)}, |
в |
= |
{К, |
L , М, |
N}, |
Г0 |
= |
{А, |
В, С, D; Е, F, G, Н; |
|
|
К, L , М, N; |
О, Р, |
R, |
Т). |
||
Поскольку |
условие |
|01 •< | Уг |
— |
|||
— со (S) | |
не |
удовлетворяется, |
то |
|||
принимаем Уг = {0, |
1, 2}. |
Теперь |
||||
неравенство |
| G | < ; | Y\ — со (S) \ |
|||||
выполняется. Определив отображе |
||||||
ние |
у соотношением |
у (К, |
L , |
М, |
||
N) = |
(0, 2), |
можно |
доопределить |
|||
функцию выходов автомата Ж 1. который представлен на табл. 22.
Из табл. 22 видно, что
П Л |
= {Л75; ~C7D; Е~7Н; |
T\G; К, |
L , М, N; |
OJ5; |
R/T}. |
Поскольку сеть J£l связна относительно |
автомата |
А\ и Го >- Пд, |
|||
то она компонентно-диагностируема. |
|
|
|
||
5.4. |
Последовательная и |
параллельная |
|
|
|
компонентно - диагностируемая декомпозиция
В данном разделе будут определены достаточные условия сущест
вования некоторых видов компонентно-диагностируемых |
сетей |
без |
||||||||||||||
обратных |
связей, которые реализуют |
поведение состояний |
сильно |
|||||||||||||
связного |
автомата. Кроме того, будет предложен метод построения |
|||||||||||||||
таких сетей. |
|
Пусть даны |
автоматы |
Медведева |
|
= |
(51 ( |
|||||||||
|
Определение |
5.4. |
At |
|||||||||||||
X, |
6J, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А2 |
= (S2 , Sl f |
х |
X, б2 ), |
...,An |
= (S„,S1xSax |
• • • x V |
i |
х X, |
б„), |
|||||||
множество выходных символов Y и функция |
выходов |
Л : ^ х <S/j |
X |
|||||||||||||
X |
X - > Y. |
Тогда |
последовательным |
соединением |
автоматов |
|
А1г |
|||||||||
А2, |
Ап |
с функцией |
выходов Л будем называть автомат |
|
|
|
||||||||||
|
|
|
|
|
М = \ х |
Sh |
X, |
Y, |
А, |
Л |
|
|
|
|
|
|
|
|
|
|
|
|
4 = 1 |
|
|
|
|
|
|
|
|
|
|
где A((sx , |
|
sn ), х) |
= (61(s1, |
х), 62 (s2 , sv |
х), |
6n (sn , slt |
s„_i, |
|
x)). |
|||||||
|
Схематическое представление такого соединения автоматов пока |
|||||||||||||||
зано на рис. 15. |
Пусть даны автоматы Медведева Л х |
= |
(Sl t |
|
X , |
|||||||||||
|
Определение |
5.5. |
|
|||||||||||||
6\). А2 = |
(52 , X , б2 ), |
Л„ = |
(5Л , X, 6 J , множество выходных сим- |
|||||||||||||