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

зует А, то через Ж = (V,

X,

Y, А, Л) обозначим

подавтомат ав­

томата ^.эквивалентный

А.

Будем говорить, что абстрактная сеть

Ж, реализующая автомат А, связна относительно А,

если для лю­

бого s € V существует р

£

X*

такое, что A (s, р) £

V.

неисправности і-й компоненты

/-м

способом, применим символ Ж\-

Автомат, определяемый

сетью

ЖІ,

обозначим через Жі

= (V'i,

X,

Y, Д-, Л{). Из свойств , 1 ,

2 и 3

простых неисправностей

непосред­

ственно следует, что класс сетей, получающихся в результате

все­

классом простых неисправностей сети Ж

и обозначим через

{Жі}

{і € Л / € J[)-

Пусть

/ — произвольное

непустое

подмножество

номеров (индексов) компонент, т . е . i s

/ и j ^ t

0 .

Определение

5.2. Абстрактную сеть Ж с

классом

простых

неис­

правностей {Ж'І}

будем называть компонентно-диагностируемой от­

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

?= /, если простым экспериментом с любой

сетью 6? из множества

{Ж} U {Жі}'

сети

номе­

а) можно установить, исправны ли компоненты

ра которых

принадлежат У;

б) можно

найти неисправную компоненту, если установлено,

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

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

а неисправности

сети — простые, то она контролируема. Будут

стояний s £ V и t £ V{. Поскольку сеть Ж

связна относительно ав­

томата

А,

то

существует

р £ X*

такое,

что

Д (s,

р)

£

V.

Пусть

s'

= Д (s,

р)

и ї = Д'- (t,

р).

Легко видеть,

что состояния

s' и

f

эквивалентны. Положим

А =

(S,

X,

Y,

б, К). Тогда существует

а £ S, эквивалентное

s' и f.

Пусть а

=

(J

Д^ (f,

q).

Поскольку

ч£Х'

а — стабильное подмножество состояний

(см. раздел

4.5) автомата

Жі,

то ему соответствует

подавтомат

М\ =

(а, X,

Y,

Д{, Л;) авто­

мата Ж'і- Покажем, что А и Щ эквивалентны. Пусть а' £ S

произ­

вольно,

тогда

ввиду

сильной

связности

автомата А

существует

рх

£ X* такое, что а'

— б (а, рх)

и t" = М

(f,

рх) эквивалентно

а'.

Обратно,

пусть

tx £ а

произвольно,

тогда

в силу

определения

а

существует р2 € X* такое, что tx

= А'

(Ґ, р2).

Но at = б (а, /?2)

является состоянием А и эквивалентно

tx.

сети Ж простые,

С другой стороны, поскольку

неисправности

s = / ( r < ) « . p r < ( s ) =

prt (0-

(5.1)

Разбиение П Л множества V зададим выражением

s = t (Пл ) <-> Л (s, х) — Л (t, х)

для всех х£Х.

(5.2)

s = t (Пг • П2 )

s s= t ( i y /\s.=

t (П2 ).

Произведение

всех

элементов

некоторого множества

разбиений

Ф обозначим через ПФ. Для непустого подмножества J номеров

компонент сети Ж определим разбиение ф (J) множества

состояний

V автомата Ж'

Ф ( / ) =

П {Г,| г"Є^}-

(5.3)

Пусть [At}, і £

I — множество компонент сети Ж- Тогда

говорят,

что Лу есть предшественник Л,- тогда и только

тогда, когда /' £

lt

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

І( дано в разделе 5.1), т. е. когда вход

At

зависит от состояния

А-г

Говорят, что непустое подмножество ком­

биение П множества состояний автомата А =

(S,

X,

Y,

б, К) имеет

свойство

подстановки, если

s == t (П)

б (s,

х)

=

б (t,

х) (П) для

всех х £

X. Индукцией по

длине

входной

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

s = t (П) -»- б (s, р) == б (t, р) (П) для всех

р Є X*.

(5.4)

Пусть i|) — взаимно однозначное

отображение,

которое

каждой

компоненте сети ставит в соответствие ее номер,

т. е. г]) (Ас) — і.

Покажем,

что

если подмножество компонент Л

сети Ж замкнуто

и непусто,

то

разбиение ф (ф {Л))

множества

состояний

автома­

та Ж имеет свойство подстановки. Прежде всего

заметим, что из

(5.1) и (5.3) следует справедливость

соотношения

s =

t (Ф(ф {Л))) «-* р Г , (s) = рг£ (t) для всех

і Є і|з (Л).

(5.5)

Пусть

s =

t

(ф (a|> (c/Z))),

s =

(su

s2 ,

s„)

и

* =

(4,

f2 ,

Докажем, что для произвольного х £

X A (s, х) == Д (f, х) (ф (ф (А))).

Поскольку

s

и

/ находятся в одном классе разбиения

ф (ф

(А)),

то из (5.5) следует, что для любого

і £ ilp (A)

s(- = tt. Кортеж

(alr

а 2 , a k ) условимся обозначать символом

X аь

где J —

( 1 , 2 , k ) .

На основании

определений

функций

переходов

А и б,- находим,

что A (s, х)

=

X 6, (s,,

х

S:, х)

и

Д (t,

х)

=

х

б> (*м

X

х).

'Є/

/£/(

«є/

/є/,-

Пусть

і £ -ф (c/Z) — произвольно, тогда

At

£ А

и /, є

ij) (сД),в

си­

лу замкнутости

множества <Л. Поскольку st

— ts и sy =

^ для

лю­

бого

j Є /,-,

то

б, (Si,

X s.-,

х) =

б,- (t[,

х г1.-,

х). Так как имеет

место

соотношение (5.5), а

і

£ ур (А)

было

выбрано

произвольно,

то состояния

Д (s, х) и Д (t,

х) находятся

в

одном

классе разбие­

ния ф (ф (А)),

что и требовалось

доказать. Отметим, что этот

ре­

зультат другим

способом доказан в работе

[60].

6(s, е) =

е,

б (s, рх)

= 6 (s, р) б (б (s, р),

х),

где s £ S,

х £ X

и р £

X*.

Пусть Пх и П2

— разбиения одного и того же множества. Будем

писать

I I j - < П2 ,

если а =

b (Еу

влечет а

Ь (П2 ).

Теорема 5.2. Пусть абстрактная сеть Ж,

реализующая

сильно­

связный автомат А — (S, X, Y,

б,

Я), связна относительно

Айв

сети возможны только простые неисправности. Тогда, если

подмно­

жество ее компонент А замкнуто и ф (ф (А))

; > Пд, то сеть Ж ком­

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

относительно множества номеров \р (А)..

Д о к а з а т е л ь с т в о . Для доказательства того, что простым

экспериментом с сетью

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

{Ж]

U

U \Ж\)

(і

Є Л І € Jd,

можно

установить,

исправны

ли

в

ней

компоненты с номерами

из я|> (А),

достаточно показать,

что двух­

элементный класс

автоматов

{Г({Ж}

U {ЖІ}),

Т({Ж))){к£1-Ъ(<А),

l£Jk, г£хЦА),

u£J,)

что

{Жк,

Ж")

также исключительный

класс.

Пусть

s и

t —

произвольные состояния в автоматах Ж'к и Ж" соответственно. В

си­

лу

свойства 3 простых неисправностей сети Ж,

можно заключить,

что s и

t

являются состояниями автомата Ж-

Предположим, что существует х £ X,

для которого

Л (s, х) Ф

Ф

A (t,

х). Учитывая справедливость равенств Л (s, х) — АІ (s, л:) и

Л (/, х)

=

Л" (t,

х), приходим к выводу, что состояния

s в ЖІ и t

то {ЖІ, Ж'к) есть исключительный

класс.

Пусть для всех х £ X

A (s, х) =

Л (t, х). Тогда

s== t (Щ)

на ос­

новании (5.2), а так как

ср (т]э (А))

> Пл, то s =

t (ср (ф {А))). По­

скольку согласно теореме 5.1 автоматы Ж и Ж" составляют

исклю­

что Л (t, р) Ф Л" (t,

р). Из этого соотношения

и

свойств

простых

неисправностей следует, что существует такая

начальная

часть q

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

р, для которой ргЛ (A (t,

q))

Ф ргЛ (Л" (t, q)).

быть, разбиение ср (ф (А))

имеет свойство подстановки. Поэтому

на

основании (5.4) и (5.5) с

учетом того, что г £ ф> (А),

получаем

ра­

венство рг, (A (s, q)) = prr (A (t, q)). Так как

k (£

г|э (А), то вход

г-тл компоненты сети не зависит от состояния

k-їл компоненты. При­

prr (A (s, q))

=

рг, (A'k (s, q)).

Таким

образом,

ргг (Д£ (s, q))

ф

Ф prr (A" (t,

q))

и, значит,

Alk

(s, q) Ф A" (t, q) (ф (яр (Л))).

В силу

неравенства ср (Ф (А)) >

Щ заключаем, что существует х' £

X, удов­

летворяющий

соотношению

Л

(АІ (s,

а), х') Ф

А

(А" (/,

q),

х').

Но тогда на основании четвертого свойства простых

неисправностей

получаем соотношение

ЛІ (s,

qx')

Ф

A" (t, qx'),

которое

доказы­

вает неэквивалентность

состояний

s и t в автоматах Жк и Ж" соот­

ветственно.

Теперь остается доказать, что если номер неисправной

компо­

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

{А), то его можно найти простым

экспериментом с сетью it

£ {Ж'І}

(і Єф (A), j £ J t ) . Для этого достато­

Зафиксируем

произвольные і, k Є 'ф [А),

і Ф k, / £ J c ,

I £ J k и

установим,-что произвольные состояния s в ЖІ и / в Жк

неэквива­

лентны.

В случае,

когда s ф

t (ПЛ ), состояния

s в Ж\ и t в Жк неэкви­

валентны.

Предположим, что s =

t (ПЛ ), тогда s =

t (ср (ф (А))).

Поскольку

класс,

то

существует такая входная последовательность р,

что

A (s, р)

Ф

А\ (s, р). Тогда из свойств простых неисправностей

сле-