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

Отметим,

что

события Hku (k =

1,

2,

...) несовместны.

Нетрудно

видеть, что

N

.-. •

PNU

(R (S', t')lp) =

1 -

'

(4.15)

2 Рка (Ньиір).

ft=l

Так

как

ш

Є

R

(s', і') -»- w£

(Qs)p,

то

P W u

(R

(s',

t')/p)

<

•P^u ((Qs)p/p)-

В силу

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

А

по

разбиению

П

lim PNtt

((Qs)p

Ip)

= 0 и поэтому

l i m P W u

(#(s\

i')/p)

-

0.

Та-

ким образом, из

(4.15) получаем

oo

=

1. На

основании

V

PkU{Hkulp)

со

(4.16)

m\s',t'/p)=

^kuPku(Hl!u/p).

*=і

Для

получения

верхней оценки

величины

т Is', i ' / p l рассмотрим

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

( £ = 1 , 2 ,

... ) , гдеРд, —услов­

ная

вероятность

распознавания

состояний

s'

и

в £-м опыте,

если

в предыдущих k — 1 опытах

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

этих состояний

Рк

связана

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

PkU(Hku/p) =

u(R(s',

t')lp)

Pk.

(4.17)

Вероятность

Рки (Hkulp)

можно

найти по

формуле

Ры

(нки/р)

=

2 (Р (pjp)

2 Р

(pjppj),

где P l € R

(s', t'),

P l

1)H | P i

D,

(R (s\ i'))Pl,

d (Pl)

=

(k-

І

d (p2)

=

u.

Из

(4.14)

и

(4.2)

следует,

что

У^Р

(р2/РРі)

>

є",

а так

как

Pi

P{k-\)u(R

(s',

t')lp)

=

'£Р

( P i / P ) ' т

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

(4.17) получаем

P i

ft

неравенство

Pf t >

є". Пусть

=

^

Р(и (Н,-и/р).

Индукцией

по

k

покажем,

что

(4.18)

gk=\~{\-Px)i\-P2)

...

(l-Pk).

во внимание, что Р0

(R

(s',

tk)/p)

=

1, т. е.

g1=:Pa(Hu/p)

= P 1 = \ - ( l - P 1 ) .

Предположим, что соотношение

(4.18) выполняется при k =

/. Тог­

да, учитывая, что Pju

{R (s',

f)

Ip)

=

1 — g t , получаем

8Ш = 8i + pi+v

и (Hu+»

ulp) =

g, +

Pju (R («', ПІР) Pi+i

=

T ft + ( !

-

si) Pi+i

=

si ( i

-

Pi+i) + P;+1 =

= (і - (і - PJ ( Г - P 2 ) . . . (і -

p,)) (і - л + і ) + Pj+i =

= l - ( l - p 1 ) ( l - p 2 ) . . .

( l _ p / ) ( l - p / + 1 ) ,

Pku (Hkufp) = (1 - g*-i)

= О - Рг) (1 - Я8 ) . .. (1 - Р*_,) P F E .

оо

что 2

О — Л )

О — ЛІ)---(1 — -Pft-i) Рь =

1 (здесь Р0 принимается

равным

0), находим

m[s',t'/p]

= u 5 А ( 1 - Р х ) ( 1 -Р2)

. . . (1 — Р*_і) Я* =

оо

т [s', t'/p] < и 2 0 — є")* = "Є-".

(4.19)

М [D] < и0и'е-"'.

(4.20)

Здесь символ Ds заменен символом D, так как оценка

математиче­

ского ожидания не зависит от фактического начального состояния

автомата.

Отметим, что верхняя оценка величины М [D] может быть уточ­

нена следующим образом. Пусть разбиение П множества S0 состоит

из классов K i , К2,

Km- Без потери общности можно предполо­

жить, что с = | Ki | <

| К21 <

• • • < | Кт \. Аналогично доказатель­

ству соотношения (4.20) легко показать справедливость

неравенства

М \D] <

(л0 — с) и'вг*.

(4.21)

-

Пусть

(X х Y)*

— множество

всех

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

сим­

волов

из

X

X У конечной

длины, пополненное пустой последова­

тельностью.

Полагая,

что имеет место

исс

X

А

7

тождество

( хг,

ух)

(х2,

у2)...

(хк,

ук)

=

=

{ххх2...хк,

ухуг...

ук) для (xt,

yt)

€

X

X

X Y (1 <

і <

k),

множество

(X

X

Y)

*

будем трактовать так же, как множе­

В(А)

ство всех пар

(р, а)

таких, что р £

X*,

q£Y*

и d (р) =

d

(q).

Пусть

П =

{Ki,

К2,

Кт)

—

раз­

Рис. 11.

Схема проведения

биение множества начальных

состояний

S0

автомата А

и контролирующий

авто­

вероятностного эксперимента.

мат В (А)

является

автоматом

Мура,

у которого состояния отмечены символами

1,

2,

m,

m

+

1.

Если

(р,

q) £

(X

X Y)*

— такая

пара

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

по которой

можно

определить,

что

начальное

состояние

иссле­

дуемого

автомата

А

принадлежит /(,,

то

автомат В (А)

должен

автомат

В (А)

перешел в состояние,

отмеченное символом

і, то

по

этой паре можно установить, что начальное

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

А

принадлежит

Кг

Определяем В (А) =

((5s (S))m,

X

X Y, І,

Д, (І, ав ), где

множе­

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

(5s

(S))m

является

/л-й декартовой степенью

множе­

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

множества 5,

X X

Y — входной

алфавит, /

=

= {1, 2,

m, т +

1} — выходной алфавит, а0 = (Ки

/С2 ,

Кт)

—

Д ((аг, . . .

,

а„

. . .

, а т ) , (х,

у))

=

f (аг

at

aJ ,

если

асф

0

и

а ;

= 0

для

1 < / < т

и

\Ф'ь,

(аі,

. . . , От)

В ПрОТИВНОМ

Случае,

где о\ = [s£

S\3t£<Jl{s

=

8(t,

x) Л Ч*> х) =

у)}

для

l < i < m .

И<*і

°i

О

=

ft, если

о,- Ф 0

и а,- = 0

для

1 < j < ; m и / і,

1 г а + 1

в остальных случаях.

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

формулы

А((al t ...

,

at, ...

, aj,

(р, q)) =

Uov

... , ait

...

, am),

если

at

Ф 0

и о,- =

0

=

для

1 <

/ <

m и / =^= і,

((аи

. . . , а т )

в противном

случае,

где а]- = (s £ S | 3 / Є а . (s =

6

(t, p) Л Ь

p) = ?)} для 1 <

і < m.

по которым можно определить,

что начальное состояние исследуе­

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

Формально

^

= {(р, q) £ (X X

3 u s

d ( Р , 3 s e K . (X(s, /,(р)) =

lk(q)

Д

„A'*s (П)

На основании определений функций А

и [х можно

показать, что

событие

5й, представлено в автомате В (А)

выходным сигналом

і,

(р, д) Є Я»,«-» |i (A (ст~0, (р, ?))) =

І.

(4.22)

Действительно, пусть (р, q) £ J 5 , . Тогда

найдется такая начальная

часть (р', g') £ (X

X

К)* пары последовательностей (р, (7)

и такое

s £ Kt,

что І

(s, р') =

<?', а для всех / Ф

і и всех

t £ К/ І

(t, р')

Ф

Ф

q'. Поэтому А (ст0, (р',

q')) =

( 0 ,

0 , ст„ 0 .

0 ) , где ст, —

некоторое непустое множество. Из определения

функции А следует,

что А_(ст0. ІР, д)) =

( 0 .

0 ,

сг£,

0 ,

....

0 )

и, таким

образом,

|1 (А (ст0, (р,

?))) =

£.

Обратно,

пусть

ц (А (ст0, (р,

д))) =

і.

Тогда

А (ст0, (р, а)) —

~

( 0 ,

0 , стг, 0 ,

0 ) , где ст( —некоторое

Непустое множе­

ство, и существуют начальная часть (р', д') £ (X

X У)* пары по­

следовательностей (р, 9) и состояние

s £ Кі такие, что X (s, р') =

д'.

Для всех / Ф

і и t £ К,Х

(і, р') Ф

д'.

Таким

образом, (р, д) £

и

равносильность

(4.22)

доказана.