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

Plt+l)

г (QJe)

=

2

(Р (pje)

2

Р (р2/рг))

= 2 Р (Рг/е) Р Г

№3)М,

Pi

PJ

PI

где

pi Є Qs>

d (px ) = t>,

p 2

£

(Qs )P l

и

d (p2 ) = r.

Поскольку

^>

iQJe)

=

2

^

^ i Є Qs- d 0°i) =

г> )> то

на

основании

(4.6)

Pi

и предположения индукции

получаем

неравенство

РЦ+D г (QJe) •<

•< (1 —єГ )'+і,

которое завершает доказательство

(4.7).

Учитывая

(4.4) и (4.7), легко показать справедливость

неравенства

Pk(Qje)<(l

-

ф

]

,

(4.8)

где [—1 — целая

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

k

на г.

Так

как 0 <

є <

1, то

из

г

следует

(4.8)

/ > ( Q s / e ) < l i m ( l — e ' ) t ' l = 0 ,

а в силу того, что Р

(Qs/e) >

0, приходим к

выводу, что Р (Qs/e)

=

0,

и теорема

доказана.

4.2.

П р о в е р к а

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

автомата

Покажем,

что

для

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

конечного

слабоинициального

разбиению

П проверяется

конструктивно. Рассмотрим бинарное

отношение

p g S Х 5 , заданное

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

(s, ОЄР - ^Н РЄ*» ( ( 6

( S > Р)

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

б (г, р)) Д

f\X(s,p)

= X(t, р)).

(4.9)

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

отношений р0 , P l )

Р і ,

которую

определяем рекурсивно

следующим образом:

(s, t)Є р , 3 , є х ( ( б

(s, x),

б (*, x))£ р,_, /\ X(s,

х) ~

X(t, х)).

P o < = P l ! = ••• = р , =

(4.10)

ливаем

базис

индукции:

(s, t)

£ ро

(s

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

0-*-V«e*((^ (s> х)

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

б (t, х))

Д X (s, х) =

X (t, х))

Я х £

Х ((б (s, х), б (t, х))

£р0АХ (s, х) =

6*

83

=

Я (t,

*))<-» (s, t) £ рх

и, следовательно, p0 s

px . Пусть

p,-_i g=

pL.

Докажем,

что

pf

g= p,+j. Действительно,

(s, 0 € Pi

Н*Є* ((5

(s. X),

б (f, x)) б p,_, Л X (s, x)

= X (t,

x))

Н*є* ((6 (s, x),

б (t, x)) £ p, Л

* (s, л-) = X (*, x)) <-> (s, 0 Є Рч-і

и поэтому р( s

р і + і .

Легко показать, что если для некоторого і выполняется равенство

P; =

р , + ь

то

рі =

рі+ь, где k — произвольное

целое

положитель­

ное

число.

Бинарное

отношение рг , удовлетворяющее

равенству

Pi =

Р(+ 1 ,

обозначим символом р. Такое бинарное отношение в

це­

почке (4.10) существует, так как множество 5 конечно. Покажем,

что р =

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

бинарных отношений можно

по­

казать, что для произвольного і

выполняется

соотношение

(s,

і) g

pi <-> ЗрЄ х« (d (p) <

і Д

(б (s, р)

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

б (t, р))

Д

—

Л Ms, P) = b(t,p)).

—

(4.11)

0 0

Поскольку p =

(J Рг. TO из (4.9) и (4.11) следует, что р = р.

1=0

Легко видеть, что бинарные отношения, входящие в цепочку

(4.10), рефлексивны и симметричны. Под шагом будем понимать

процедуру

построения

рі+і

по

р,

и таблице переходов

и выходов

автомата.

Тогда,

учитывая,

что | р | <

л2 , | р01 >

п и | р/| > п + 21,

если

р, Ф

Pi—i,

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

требуется

не более, чем п (п — 1)/2 шагов.

Пусть p S o

=

р П S0

X S0 , а я — отношение

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

множестве

S0,

соответствующее разбиению П. Тогда теорему

4.1

можно

переформулировать

следующим

образом.

Слабоинициальный автомат А с разбиением П множества на­

чальных состояний диагностируем

по разбиению П тогда

и только

тогда,

когда

ps „ s

я.

Действительно,

p S o s= л <-»• y S i , ((s, t 6 S0 Д

Л НРЄХ* ((б (s, р)

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

б (t, р))

Д Ms,

р) = X (t,

р))) ->- s Е=

=

t(U))*r+

Vs.<6s.As*<(n) VP£X*(Ms .

p) = M*. P)->(6(S, p) не эквива­

лентно б (£, /?))). Если

автомат

Л — приведенный,

то

эквивалент­

ность

состояний

s и

t равносильна тому, что s =

t,

и

проверка

автомата на диагностируемость по разбиению упрощается.

Для иллюстрации процедуры проверки диагностируемое™ ав­

томата по разбиению рассмотрим автомат А, который задан

табл. 12.

Т а б л и ц а

12

а

р

а

Р

а

Р

а

Р

1

5

1

0

0

6

9

7

0

1

2

6

2

0

0

7

6

10

1

0

3

7

3

1

0

8

7

10

0

0

4

8

4

1

0

9

9

9

0

1

5

9

6

0

0

10

10

10

1

0

строим

бинарное

отношение

р.

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

отношений

р(. (t

=

0, 1,...)

будем

по­

Т а б л и ц а

13

лучать на матрице

размер­

1

2 3

4 5

6 7

8 9

10

ности

10 X 10,

у

которой

строки и столбцыотмечены

1

0

2

2

2

2

состояниями

автомата

А.

На пересечении

s-й строки

2

0

2

2

2

3

0

2

2

и ^-го столбца, будем

ста­

4

0

1

1

2

вить

такое

и

число

і,

что

5

0

(s, f)

€ р;

(s,

/)

$ р,-_,.

6

0

1

Бинарные

отношения

pt

7

0

1

1

строятся на матрице после­

8

0

1

9

0

довательно,

начиная с

р0 ,

0

10

начальных состояний является диагностируемым

по разбиению П

и находится в начальном состоянии

s, которое

экспериментатору

не известно. Пусть для произвольной

последовательности w lk(w)

Пусть / — натуральное число, пй — \S 0 1, п =

\S\и. г =

(п0 — I) X

X (п — 1).

Определим

множество

G% =

{p6X*\d(P)

= \г Л hi-i)r(P)eQs

Л Р €

Qs}-

Р $. Qs-+ Pw £ Qs Д л я

в

с е х w € X*.

(4.12)

Условимся событие, заключающееся

в

появлении на

выходе ис­

события G}r

(/

=

1, 2,....) несовместны. Поэтому на основании (4.12)

можно показать, что для произвольного натурального N выполня­

ется

соотношение

N

2 Pjr(Gsir/e)=

l-PNr(Qje).

Поскольку

автомат

А

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

по

разбиению

П,

то

\imPNr(QJe)=

0 и поэтому 2 Л > ( С / г / е ) = 1. Так как P,r

(G-r/e)

=

А/-+СО

Р (We)>

Р

/ = 1

Gs =

U G)r. Кроме того,

= 2

т о

2

(р/е) = 1. где

p£cF.r

р£&

/='

множество входных

последовательностей (2s можно

принять в

ка­

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

элементарных

событий.

Пусть р £ G3,

«0

= п0—

1 и и =

п— 1. Длина

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

ности

р пропорциональна

числу г =

щи, т. е. d (р) = ku0u,

где

k —

некоторое

натуральное число.

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

(q £ X*), определенное в раз­

ней мере два класса, то о£ Ф

0;

но в силу

того, что р не принадле­

жит множеству Qs, ар =

0 .

Разобьем

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

и0

подпоследовательностей так, чтобы р =

PiP2---pu„

и для 1 <

І <

и0

d (pi)

=

iiu. Натуральные

числа

/,

определим рекурсивно.

В

ка­

честве

/ j

примем такое наименьшее

целое

число, что в$е Ф

rf.

w .

'І

Предположим, что числа у'х, /2 ,

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

самым,

определены подпоследовательности рг,

р2,

рі—\. Найдем

число

а

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

pt.

Если

GplPt...P[_1

ф

0,

то jt положим

равным такому

наименьшему

целому

числу,

что

<£,!>,...«-1=?*=

-••+/,)«»)• Е с л и

ж е

=

0 - т о

h примем

равным числу

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

в последнем

слу-

На множестве (Т

определим

числовые

функции

d * ( l < ! i - < « 0 )

следующим образом:

d\{p)

= d{Pi),

где pt — подпоследовательность

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

р, определен­

ная выше. Пусть Ds

также

числовая

функция на

Gs такая,

что

Ds (р) = d (р). Рассматривая

функции

Ds

и d\ (1 •< і •< и0)

как

+ ds,h, на основании теоремы сложения

математических ожиданий

получаем

М [Ds\ = т[df] +m[dl]+

• • • + т[dsUo],

то

Если найдем такое число h, что для і =

1, 2,

и„ т [d\\ <: h,

M [ D s ] < u 0 f t .

(4.13)

Пусть

t ё S0

и t щ£

s (П). Пусть

р—такая

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

выданная источником,

что Я (s, р) =

Я (/,

р). Обозначим

s'

= б (s,

р),

Г =

б (£,

р) и

/л Is', Г/р] —математическое

ожидание

длины

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

кратной и, которая

различает состояния s'

и f

у если на выходе источника уже появилась последовательность р.

На основании теоремы 4.1 получаем, что состояния s' и f

не экви­

валентны и

Vo>ex* Н^Є^'Л" (аГ) =u(^(s'» w) = k(f,

w)-+X(s',

WW') фХ(Ґ,

ww')).

(4.14)

которых заключается

в наблюдении

входной

и соответствующей

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

длины и.

Пусть R (s', t') =

{ w £ X* І Я,

(s\

w) = К (f,

w)}. Символом # t o

которых не принадлежит множеству R (s't f),

но любые ее началь-

ные части длины и, 2и,(k—

1) и принадлежат R(s', ?). Из опре­

деления R (s\ t') следует,

что оно вместе с любой последователь­

ностью из этого множества

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

этой

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

Поэтому

Hku = [wЄX*Id(w)

= ku Л hk-i)u(w)£R(s\

f)f\w£R(s',

0} -