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

дует

существование

начальной

части

q — q'x

(q'

£

X*,

х

£ X)

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

р ,

удовлетворяющей соотношениям

рг, (Д (s, q ) ) ^ p r , ( A i ( s ,£/)),

(5-6)

-

=

-,-

q').

A(s,q')

A{(s,

Допустим,

что рг,- (ДІ (t,

q))

=

ргг

(Д (t, q)).

Из

соотношений

(5.4),

(5.5)

и

і

£ ф (А)

получаем

ргг (Д (s, (7)) =

рг, (Д (t,

а)).

Тогда,

учитывая

(5.6),

находим,

что pr;

(Д, (t,

q)) щк рг, (А[ (s, q)).

Если

=

АІ

(t,

q)

и

s'

=

Д{- (s, 7), то s' ^= f

(ф (ф

(А)))

и,

сле­

довательно,

существует

х'

Є X

такой,

что^ Л (У, х')

Ф Л (f,

х').

Отсюда

получаем

соотношение

Л[- (s,

qx')

Ф

А{

(t,

qx'),

которое

доказывает неэквивалентность состояний

SH t в автоматах Ж\

и ЖЇ

соответственно.

Пусть теперь pr, (Ak (t,

q))

Ф ргг (Д (t,

q)).

В этом случае долж­

на существовать, начальная часть q" последовательности

q такая,

что

Ч"Ф

q

и

pr t (At (t,

q"))

Ф

рг, (Д (t,

q")). Из

(5.6)

следует,

что

Д'

(s,

q")

= Д (s,

q"),

а на основании

соотношений (5.4),

(5.5)

и k £ ф (А)

можно утверждать справедливость равенства

pr, (A (s,

q"))

=

рг, (Д (f,

q")).

Поэтому

рг, (Д, (*, <?")) ^= рг,

(Д{ (s,

q")).

Если

Г

=

Д, (t,

q")

и

s" =

Д{ (s, g"),

то

s"

Ф t"

( Ф

(і])

(А))),

и так же, как в предыдущем случае, легко показать

неэквивалент­

ность состояний s и t в автоматах ЖІп

Jfjl. Теорема

доказана.

Непосредственно из теорем 5.1 и 5.2 вытекает

следствие.

Следствие 5.1. Пусть

абстрактная сеть j f , реализующая

сильно­

связный автомат А,

является

связной

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

автомата

состоит из п компонент и можно выделить замкнутое

множество

компонент А такое, что | А | =

п — 1 и ф (яр (А))

>• Пд, то сеть Ж

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

Отметим, что необходимым и достаточным условием

компонент­

ной

диагностируемости

сети Ж

относительно множества

номеров

Ф (А)

ее компонент является

исключительность класса

автоматов

Э П = {Г({#{}/ЄУ( )}<ЄФИ>

U {Г({Ж)

U { Л ё Ч < А ^ ) Ь

где Г ({Ж'с}/^.) — сумма автоматов, соответствующих

различным

неисправностям t-й компоненты; Г ({Ж}

U {Жк)к@у

(A. tGJk)

— сум­

ма автоматов, одним из

которых

является автомат Ж, а

остальные

а = Ь (Ms~s (Тд) -^8(а,х)~о

(b, х) (Г{)

для

всех

х £ X, (5.7)

a Mx-s (Г,-) — такое наибольшее разбиение множества

X,

что

x=£y(MX-s(Tt))^>-6(a,x)==&(a,

у) (ГЦ

для

всех

a

£S.

Теорема

(Хартманиса — Стирнса). Пусть даны автомат А

=

= (5, X, Y,

б, X), разбиения Г,, Р,-,;- множества S и разбиения

М,

множества X для 1 •< i, j •< л. Сеть % в стандартной

форме та­

кая, что Ж реализует поведение состояний А и Г,-, Р,-^, М;

являются

тогда,

когда выполняются следующие

условия:

1)

Г,-П Р/.,-< A f s _ s (Г,-)

для

всех

і;

і

2)

М,- < Mxs (Г;)

для

всех

і;

3)

Р£ ; - > - Г,-

для

всех

і и /;

4)

П'ГЛ = 0.

г

следующей

теоремы.

Рассмотрим вопросы, связанные с построением компонентно-

диагностируемых

сетей. Аналогично

(5.2) определим разбиение Щ

множества

состояний автомата

А.

Теорема

5.3.

Пусть

{Г,} (1 •< і •< п) — семейство

таких

не­

тривиальных

разбиений

множества состояний

сильно

связного ав-

томата А =

(S, X ,

б, X), что Г0

л—1

Г, имеет свойство под­

Y,

= П

п

ілі

становки, Г0

>

существует

компонент­

П*. и Г — П Г, = О. Тогда

ів

но-диагностируемая

сеть J t , состоящая

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

(і-я компо­

нента имеет | Гг | состояний)

и реализующая

поведение

состояний

автомата

А.

{Р*,у}

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

(1 < ; i, j <

я) множества S следующими соотношениями:

J?i,t

=

I

для

£ = 1,2, . . .

,

п;

Pij

=

Г,

для

і, / =

1, 2

п — 1

и іф j ;

Р,,„ =

Г,

для

t ' = l , 2 , . . .

,

л — 1;

Р л У

= і

для t = l , 2 ,

. . . ,

п — 1.

Пусть, далее, разбиения Мг множества

X таковы, что

Ш1

= О

для всех і (1 < : і <С п). Покажем, что разбиения

Г,-, Р/,/ и М( удов-

Г, П Р/.« = Г( РЛ ,РЛ ,, П

Р,-./ =

г ( п г ;

= "П Г/ =

Г0 .

/

І+і

ІФІ

І—1

І+п

іі-п

Так как

Г0

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

< ; Г,, то а =

Ь (Г0 ) - >

->- б (а,

х)

=з б (Ь, х) (Г,)

для

всех

х £ X.

Поскольку

Mss (Г/)

то

Г0 < MS-s

(Г,).

Если

і — п, то

Гп

П Р/.„ = ГП Р„.„ П

Р/.в = П Г/ =

Г =

О,

и

условие 1) также

выполняется. Проверка выполнения условий

2) — 4) тривиальна.

Таким образом, согласно теореме Хартманиса — Стирнса можно

построить сеть

({А[},

X,

Y, {Д./}, {fx,i},

g)

в стандартной

1-й компоненты будет Г,.

В нашем случае для

і =

1,

2,

п — 1

At

= (Г„

Хь

6,),

где

X , = 1\ X

• • • X

Г,_,

X

Г / + 1 X

• • • X

X Г„_і х

X.

Функция переходов б

определяется

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

б,-(Кг, (я), Кг, (я), . . . .

Кг,._,(а), Кт,+1{а)

Кг я _ , (а),

*)

=

где

Кг. ( я ) — класс

разбиения Г/,

содержащий

а.

Заметим,

что

функция переходов б, не определена, если

л—1

0 .

Для

|~| Кг. =

автомата

Ап

= (Г„,

Хп,

б„) принимается

Х „

= І\ х

Га

х

• • • X

X Гп _і X

X ,

а функция

переходов

б„ определяется

выражением

М Я г „ ( а ) , Кг, (а),

Кг„ _ , (а),

х) =

Ктп(&(а,

х)).

п

Функция

б„ не определена, если П Кг. = 0 . Легко видеть, что

Медведева,

т. е. Л, =

At.

Пусть а

: S

V

изоморфизм, соответ­

ствующий

построенной

реализации

поведения

состояний, где

V =

= X Г/ — множество состояний автомата

Согласно работе

[60]

а (а) = (Кг, ( а ) К г л ( а ) ) -

Таким образом, множество состояний V

подавтомата ££' автомата £6, изоморфного

А,

определяется

соот­

ношением V = a (S).

Покажем, что функции переходов компонент можно доопределить.

так, что сеть Сбудет связной относительно

А. Для этого введем в