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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.06.2024

Просмотров: 114

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Легко видеть, что Pkm(OA/S) = 1. Тогда из (4.29) и (4.30) следует справедливость неравенства

 

РКТ

(S/OA)

>

1

p(v)

j

г _ .

(4.31)

 

 

 

 

P{S)

'

k

 

 

 

 

 

 

 

Поскольку

Ркт (S/OA)

•< 1

при

любом

натуральном

k, то (4.31)

позволяет

заключить,

что

lim

Ркт (S/OA)

= 1, если

Р (S) Ф 0.

Если в результате вероятностного эксперимента контролирую­ щий автомат ТА определяет, что появившаяся пара последователь­ ностей принадлежит ОА, то будем говорить, что результат экспери­ мента положительный. В противном случае результат эксперимента назовем отрицательным. Предположим, что в случае положитель­ ного исхода эксперимента требуется, чтобы выполнялось неравен­ ство Ркт (S/OA) >• Р, где Р — произвольное положительное число, меньше единицы. Нужно определить, во сколько раз длина вероят­ ностного эксперимента должна превысить число т , чтобы выполня­ лось это неравенство, т. е. требуется найти число k, полагая, что в (4.31) правая часть неравенства больше или равна Р. Искомое k должно удовлетворять неравенству

k>

Р

P W

 

1 — Р

Р(5) •

Для определения длины вероятностного эксперимента, повы­ шающего в случае положительного исхода вероятность Ркт (S/OA) до заданного уровня, требуется знание верхней оценки числа т.

Аналогично

доказательству

неравенства

(4.20)

с

учетом

того,

что т Is]

есть

условное математическое

ожидание

длины

веро­

ятностного

эксперимента,

можно

показать

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

соотношения

 

 

 

 

 

 

 

 

 

 

 

т < л ( 2 / г — 1 ) е - ( 2 " - " .

 

 

 

Здесь е — число из соотношения (4.1),

а

п = max {|5|, \ST\, ...

\SN\},

где5;

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

Л,. Отметим, что

определенная этим неравенством верхняя оценка для т зачастую завышена, поэтому в практических приложениях следует пользо­ ваться статистической оценкой математического ожидания т. Ста­ тистические данные для определения этой оценки можно получить путем проведения вероятностных экспериментов с заведомо неис­ правными автоматами, фиксируя различные начальные состояния. При этом в качестве контролирующего автомата можно применить автомат ТА-

На практике часто имеет место случай, когда экспериментатор может устанавливать исправный автомат в фиксированное началь­ ное состояние, а для неисправных автоматов такая возможность исключается. В этом случае можно считать, что исследуемый авто-

7

2—1686

97

мат

В принадлежит

множеству

автоматов

{А, Аг,

А2,

A N ) ,

где

А — инициальный,

а

остальные не инициальные

автоматы.

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

=

(S,

X, Y,

б, X, s0) и

Г (Аи ....

AN) = (У,

X,

7,Д,Л). Из теоремы 4.1 следует, что при сделанных

предположе­

ниях автомат В контролируем тогда и только тогда, когда для

произвольных s £ V и р £ X* равенство X (s„, р) — Л (s, р)

влечет

 

 

 

 

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

состояний

б (s0 , р)

и

нес

 

 

 

A

(s,

р).

 

 

 

 

 

 

 

 

 

 

 

 

 

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

случае в качестве

 

 

 

 

контролирующего

автомата

можно

ис­

 

 

 

 

пользовать

инициальный автомат А сов­

 

 

 

 

местно с устройством сравнения выход­

 

 

 

 

ных

сигналов

и схему

проведения

ве­

 

 

 

 

роятностного эксперимента можно пред­

 

 

[УС

 

ставить

в

виде,

 

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

на

 

 

 

рис. 12, где ЯСС — источник случайных

 

 

Т

 

 

 

 

сигналов,

 

В — исследуемый

автомат,

Рис. 12. Схема контроля ис

А — исправный

инициальный

автомат

и

УС — устройство

сравнения.

Функ­

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

В.

ция

УС

заключается

в сравнении вы­

ходных

сигналов

 

автоматов

В

и А. При несравнении делается

вывод,

что

исследуемый

автомат неисправен. В случае

сравнения

выходных

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

с увеличением

длины

вероятност­

ного эксперимента происходит увеличение апостериорной вероят­ ности того, что автомат В исправен, в соответствии с неравенством (4.31).

Г л а в а 5

К О М П О Н Е Н Т Н О - Д И А Г Н О С Т И Р У Е М Ы Е

СЕ Т И А В Т О М А Т О В

Вданной главе будут рассмотрены некоторые вопросы теории экс­ периментов с сетями, состоящими из соединенных между собой автоматов (компонент). Теория экспериментов с сетями является промежуточным звеном между теорией экспериментов с автоматами и ее техническими приложениями. В настоящее время теория экспе­ риментов с сетями автоматов только начинает создаваться.

При контроле и диагнозе сети возникает задача определения ее исправности и отыскания в ней неисправной компоненты, если уста­ новлено, что сеть неисправна. Ниже будут определены условия, при которых возможен контроль исправности и нахождение не­ исправной компоненты сети, а также рассмотрены способы конструи­ рования сетей, которые удовлетворяют этим условиям.

Материал этой главы основывается на работах [4—6].

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

В качестве математической модели сети будем использовать абстракт­ ную сеть Хартманиса — Стирнса [60]. Абстрактная сеть Ж = ({Л,-},.

X, У,

{fi}>g)

представляет собой совокупность

следующих объектов:

1)

{А, =

(S,, Xh б;)}, і £ I — множество

автоматов Медведева;.

2)X — непустое конечное множество, внешний входной алфа­ вит сети;

3)Y — непустое конечное множество, внешний выходной ал­ фавит сети;

4) її —отображение множества ( х 5Л X X во множество Хь за- /Є/

дающее правило соединения г'-го автомата с остальными автоматами

сети;

 

 

 

 

 

 

 

 

5) g — отображение

множества

( х

S ) х X

во

множество Y,.

функция выходов сети.

 

 

i£i

 

 

 

 

 

 

 

 

 

 

 

Говорят, что абстрактная сеть Ж задана в стандартной форме,

если каждую функцию /, можно представить в виде

 

 

ft(sv s2,

. . . , s„, х)

=

(fi,i(Sj),

f2.i{s2)

 

/n.,(s„),

fx,i(x)).

Здесь предполагается, что

I = (1, 2,

n). В

дальнейшем будем

рассматривать только сети в стандартной форме.

 

 

Абстрактная сеть Ж определяет

автомат, у которого

множество

состояний V равно X

 

входной

и выходной

алфавит

совпадают

 

і

 

входным и выходным алфавитами сети,

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

а функции переходов А и выходов Л определяются

выражениями

Д (S, х)

= (61 (S1 ,

(sx ), . . . ,

fnA (S„), fx.! (x)), ...

 

 

• • • > б «(5я. /j.nfo), . . . .

fn,n(Sn),

fx,n(x))),

 

 

A(s,

x) = g-(slf

. . . , s„, x),

 

 

 

где s = (sx ,

sn). Условимся автомат, определяемый сетью ^ о б о ­

значать также символом Ж, а из контекста всегда будет ясно, идет, ли

речь о сети

Ж,

или об

определяемом

ею автомате Ж- В

нашем

случае Ж =

(V,

X,

Y,

А, Л).

 

 

 

 

 

 

 

В кортеже а =

(аг,

а2,

ап) его і-й элемент (1 •< і •< п)

будем

обозначать через

рг,- (а). Каждой функции ft,i

поставим в

соответ­

ствие разбиение

Р,-,/ множества

V,

определяя

его выражением

 

 

s

 

t (Ри)

ftJ

(рг,

(S)) =

f u (рг, (0).

 

 

 

Напомним, что разбиение, состоящее из одного класса, обозна­

чается через I, а разбиение, состоящее из

одноэлементных

классов,

обозначается

символом

О

(I и О—тривиальные разбиения).

 

Если Р(>;-

= I,

то это значит, что входной

сигнал /-го

автомата

Медведева не зависит от состояния

і-го автомата. В отличие от ра­

боты [60] і-й компонентной сети Ж будем называть не автомат

Аь

а автомат, образованный Л,- и функциями

для которых

P,v ф

I.

7 *

 

 

 

 

 

 

І

 

 

 

 

99

і

Пусть !, =

{ / €

І

І P/,<

ф 1}

=

(Л,

/2 ,

ik),

где А зависит

от^ І.

Тогда /-й компонентой

сети

Ж

назовем автомат

At

= (Sh

Xt,

bt),

где X,- =

(

x S.)

 

x X ,

а функция

переходов

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

соот-

ношением

 

Щ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6j(s( ,

s/,, . . . .

s/ft, Л:) = б, (sc, flt,i(Sit),

...

,

/7*.<(Ы

fx.i{x))-

На рис.

13 показана 1-я компонента

сети

Ж-

 

 

 

 

 

 

Определение компоненты сети изменено для того, чтобы можно

•было неисправности комбинационных

схем, реализующих функции

 

 

 

 

 

 

 

fi,,-,

рассматривать

как

неисправ­

 

 

 

 

 

 

 

ности

компонент.

 

 

 

 

 

 

VluL

 

 

 

 

 

Под неисправностью сети Ж бу­

 

 

 

 

 

 

дем понимать

такое

ее

преобразо­

 

 

 

 

 

 

 

 

 

 

 

 

 

 

вание, в результате которого вновь

 

 

 

 

 

 

 

получается

сеть. При

этом будем

 

 

 

 

 

 

 

предполагать,

что

указанное

пре­

 

 

 

 

 

 

 

образование удовлетворяет некото­

 

 

—

 

 

 

рым фиксированным

условиям, ко-

x°—l—ГЦ

 

 

А/1

 

торые

определяют

тип

неисправ-

I

 

 

 

 

 

 

 

 

 

 

 

 

ностей. Поэтому можно класс неис-

Рис. 13. і-я компонента сети Ж.

 

правностей

(данного

типа)

сети Ж

 

 

 

 

 

 

 

отождествить

с

классом

сетей, по­

лучающихся из

Ж в

результате всевозможных

преобразований,

удовлетворяющих фиксированным условиям. Назовем этот класс сетей классом неисправностей (данного типа) сети Ж и обозначим его символом %. Пусть 2 Ї % = [Ж] U 2*.

Определение 5.1. Абстрактную сеть Ж с классом неисправностей 21 будем называть контролируемой, если простым экспериментом

с любой сетью

из %л можно установить, является л и ^ сетью

Ж-

Напомним,

что автомат М является реализацией автомата

А,

если М содержит подавтомат, эквивалентный А. Автомат М являет­ ся реализацией поведения состояний автомата А, если М содержит подавтомат, изоморфный (по состояниям) А.

Пусть Ж — абстрактная сеть в стандартной форме и определяе­ мый этой сетью автомат является реализацией автомата А. В даль­ нейшем будем рассматривать только такие неисправности сети Ж, которые имеют следующие свойства.

1. В результате неисправности получается такая сеть, что опре­ деляемый этой сетью автомат не является реализацией автомата Л.

2. Неисправной может оказаться любая компонента Л( , но в каждый момент времени может находиться в состоянии неисправ­

ности только

одна.

 

 

 

 

 

 

 

3.

В результате

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

t-й

компоненты

автомат

At =

=

(S{,

X/, бг)

может

стать

одним

из

автоматов множества

{А{},

j

Є J t

, причем

ЛІ =

{S[, Xh

б() и S[ є

St для всех

/ £ J t .

 

Смотрите также файлы