Файл: Богомолов А.М. Эксперименты с автоматами.pdf

Теорема

5.4. Пусть {П,} (1 •< і •< п) — такое семейство

раз­

биений

со свойством подстановки

множества

состояний

сильносвя­

зного автомата А — (S, X, Y, б, Я), что 1)

1 >

> П2

> • • • >

> П„ =

0;

2) Пп_і >- Щ- Тогда

существует

нетривиальная

по­

дения состояний автомата А,

состоящая

из п компонент.

Д о к а з а т е л ь с т в о .

Из первого

условия вытекает, что

ния состояний автомата А, состоящая

из

п компонент.

Построим

последовательность

разбиений

Г\, Г2 ,

Г„ такую, чтобы Гх

=

П1

и П, =

П,_іГ,

для

2 < і

<;

п.

Легко

видеть, что

при

этом

П,

=

і

^

= П

Гj для 1 <

і <

п.

В

t'-й

компоненте Л, =

Л, =

(Г,, X,,

б,)

последовательной декомпозиции

<— і

X

М множество X, равно х Г/ X

(для і =

1 Хі

= X),

а функция

переходов

/=і

б, определяется соотно­

шением

б,- (Кг, (а), К Г і

(я)

К г , , , (а), х)

= Кг, (б (а,

х)).

і

Если

П Кг. =

0 ,

то функция

переходов б, не определена. Функ-

ция выходов Л автомата М определяется формулой

і

Л ((К Г і

(а),

Кг2

(а),

... ,

Кг„ (а)), х) = Я (а, х).

При

0

функция выходов

Л не определена.

Изоморфизм

П Кг. =

рассмотрим отображения f, : х

х

(1 < : і <

п), определяя

их рекурсивными выражениями

h (Кг,)

=

К г „

М К Г і

Кг,) =

_

(/,_,

( K r t ,

• • • , Кг,_,)Кг,),

если Д]

К г . П Кг, Ф 0,

. ( f r _ i ( K r ,

••• . Кг,_,),Кг,)

в

противном

случае,

где (Кг,

Кг,_,) = ( К г „

....

Кг,_,)

и

Кг, — некоторый

такой

класс

разбиения Г,, что

Г| Кг.

П Кг. ф

0-

Функции б

(1 < : і •< п)

доопределяем согласно соотношениям

б, (Krti

KTX

Krt_v

x) = 6, [Kvv X T V

... , /Сг,_,,

x),

где (/Сг„

/Сг£) =

А- (Лг,,

Кг,.)- Легко

видеть, что

функция

п

A(s, x)£a(S)

для всех s£ х St и х£Х.

п

Пусть

V =

х

и {Г,} (1 <С і < : п) — семейство разбиений мно-

жества

V,

в котором каждое Г,- задано согласно

соотношению (5.1).

тельстве

£ = 1

5.3,

используя

Т а б л и ц а

23

л — і

теоремы

Пусть Го =

П Г,-. Методом,

аналогичным

описанному

в доказа-

условие (2) теоремы 5.4, можно до­

0

1

0

1

определить

функцию

выходов Л

1

5

1

0

0

автомата М так, что

будет

выпол­

няться

неравенство

(5.10). При

2

6

2

0

0

3

7

1

0

1

этом

может

возникнуть

необходи­

4

7

2

0

1

мость расширения выходного алфа­

5

3

•7

1

0

вита

Y

автомата М.

В результате

6

3

6

1

0

получается

автомат

Мъ

который

7

4

6

1

1

отличается от

М только

выходным

него выполня­

алфавитом,

является связным относительно Л и для

ется

неравенство

(5.10).

Поскольку

множество

компонент

Л =

= [А\]

(1 •< і <: п —

1)

замкнуто,

то на

основании

следствия

5.1

можно

утверждать,' что

сеть, соответствующая

автомату

Мъ

является

компонентно-диагностируемой. Теорема доказана.

мере автомата Л2, заданного табл. 23.

Легко проверить, что

разбиения

l b

=

{1,2, 3,4;

5 , 6 , 7 ) ,

П2

=

{172; 3 ^

57677},

П3

=

0

г 1

=

п 1 (

Рис. 17. Схема

соединения компонент по­

Г2

= - { 1 , 2, 5, 6, 7; , 3 , 4 } ,

следовательной декомпозиции автомата А1.

Г, =

{1,3, 5;

2,4,

6;

7}.

Они удовлетворяют равенству П<- = П,-_іГ,

для

і =

2, 3.

Введем

следующие

обозначения:

Q l = l , 2 , 3, 4;

^ = 5 , 6 , 7 ;

А, =

1, 2, 5,

6, 7;

fca = 3,

4;

а3

=

1, 3, 5;

b3

=

2, 4, 6;

c3

= 7;

A = (av

a2, Q3 ); В = (alt

a2, b3);

С = (аь

a2, c3);

D — (av

b2, a3);

E = (а1г

b2, b3);

F = (av

b2, c3);

G = (blt

a2, a3);

H = (blt

a2, b3);

К = (blt

a2, c3);

L = (blt

b2, a3);

N = (bv

b2, b3);

О = (blt

b2, c3).

Для доопределения функций переходов компонент Alt

А2,

А3

и ав­

томата Мх

построим отображения

flt

f2 и f3,

которые

представлены

соответственно табл. 24, 25, 26.

Т а б л и ц а 24

Т а б л и ц а 25

Т а б л и ц а 26

А1

tel.

(ві.

b2)

Л

А

G

G

by

Ьг

В

В

Н

Н

(Ьх. ь2 )

а2)

С

А

К

К

D

D

L

G

Е

Е

N

Н

F

D

О

К

Т а б л и ц а 27

Т а б л и ц а 28

О

1

(al f 0)

(av 1)

(&„ 0)

tei, 1)

*1

«1

a2

a2

a2

Ьг

a2

«1

h

b*

a2

a2

62

a2

Т а б л и ц а 29

(аь

а„, 0) (at , а2 , 1) (а,, 62, 0) (а,, &2 ,

1)

а„,

0) (6t, а2 ,

1) (bv

Ь2, 0)

62 , 1)

а3

а3

а3

Сз

а3

°з

с3

а3

с3

Ьз

Ьз

Ьз

Сз

Ьз

а3

Ьз

аз

ь3

Сз

а3

аз

Сз

а3

ь3

Ьз

Ьз

Ьз

В рассматриваемом

примере

U=[A,

В, С, D, Е,

F, G, Н,

К],

V-U={L,N,

О},

со(5) =

{(0,0),

(0,

1),

(1,0), (1, 1)},

в =

(L, М, 0}, Г0 =

[А,

В,

С;

D, Е, F;

G, Н, К;

L,N,0).

Принимая Yx

— (0, 1, 2}, убеждаемся,

что неравенство | Є | < : | Y\ —

— со (5) | выполняется.

Задаем

отображение

у

соотношением

у (L, N, 0) =

(0, 2) и доопределяем функцию выходов автомата Мх,

который

представлен табл. 30.

Из табл. 30 видно, что

П Л

= {А, В,

С;

D, Е,

F; G.H;

К;

L , N, О}.

зультате

построения

параллельной

Т а б л и ц а 30

декомпозиции

автомата

получается

0

1

0

1

автомат,

у

которого

функция

пере­

ходов всюду

определена.

При

этом

G

А

0

0

реализация

может оказаться состоя­

А

щей

из

нескольких

изолированных

В

Н

В

0

0

подавтоматов, и сеть не будет связной

С

G

А

0

0

D

К

А

0

1

относительно

реализуемого

автомата.

Е

К

В

0

1

Поэтому

условия формулируемой

ни­

F

К

А

0

1

же теоремы

должны

обеспечить

воз­

G

D

К

1

0

можность

построения

декомпозиции

Н

D

Н

1

0

К

Е

Н

1

1

автомата, связной относительно

этого

L

D

К

0

2

автомата.

N

D

Н

0

2

Каждому

разбиению со

свойством

О

Е

Н

0

2

подстановки

П

множества

состоя­

в соответствие

автомат

ний

автомата А

= (5,

X, Y,

б, X) поставим

Медведева An

=

(П, X, бп), у которого функция переходов бп опре­

деляется равенством бп (Кп (а), х)

= Кп (б (а, х)). Автомат Лп, сле­

дуя

[601, назовем П-образом

автомата Л.

Определение 5.6. Семейство разбиений со свойством подстановки

{П;} (1 < ; і •< п)

множества

состояний

автомата Л будем

называть

сходящимся, если для произвольных классов /Сп„

Кпп

разбиений