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

ложению

индукции, для

всех хс ИЗ Кп Ц>с (s )

= Фй (s ) и для

всех

xf из Ki

q>f (s) = ф,- (s).

Поскольку фй (s) = ф,

(s), то для всех хс

sa

няется. Следовательно,

для

всех

/',

1 - < / •< (т —

1) п,

соотноше­

ние (1.19) выполняется. Из того, что для всех s O f - "

" =

/

вытекает,

что для i, h, ф, =

ф„. Значит, Л =

Л', что и требовалось доказать.

Оценим длину последовательности р, построенной по П5. Эта

последовательность состоит из трех компонент:

1) на каждом /-м, 0 - < /, шаге процедуры р,- оканчивается последо­

вательностью х[1,

и таких

шагов

(m —

1) п +

1;

2) на каждом /-м шаге, 1 •< /, к последовательности

p / _ i припи­

сывается последовательность

q-t

длины d (qfi

•< ^ " ^ ^ j ;

3) перед удалением состояния

s из множества

Т'х~1

на у'-м шаге,

О •< /,

к

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

построенной

ранее,

приписывается

символ

х.

Отсюда

следует,

что длина

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

построенной

по П5, не превосходит

(m—

1) п(п — 1)

mn +

((т. — 1) п +

1) L m a

x

+

(1.20)

и не короче

(1.21)

тп +

{(т—

l ) f t +

l ) L r a i

n ,

где

п =

\S\, т =

\Х\,

L m

a x

=

max/,-

(m—\)n(n—

1)

(Ш—1) n

•f-min

= min

l£,

v

I

—

m— 1

/ = 1

Если для всех і, h, 1 - < і,

h < : m, /(

=

/,,, то оценки (1.20), (1.21)

совпадают с оценками (1.15), (1.16) соответственно.

Рассмотрим примеры, показывающие достижимость оценок (1.20)

и (1.21).

Т а б л и ц а

6

Х1

Хо

. . .

Хт

Х-1

х% . . .

хт

1

2

4

4

0

0

. . .

0

2

3

4

4

1

1

1

3

4

4

4

2

2

2

4

1

4

4

3

3

3

Пусть автомат Л5 задан табл. 6. Последовательность х,

где л; —

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

является

для

него

диагностической.

Пусть

s0 = 3.

В случае, если т =

3,хг

=

0,х2

=

\,х3

=

2, по процедуреП5стро­

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

О6 12 22 01а 022 02 12 0а 22 03 13 03 12

длины 33,

равной оценке (1.20). Легко

видеть, что

оценка

(1.20)

достижима

для

всех

т >• 1 для Л5.

Пусть автомат Л6 задан табл. 6.

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

является

для

автомата

Л6 диагностической.

Пусть

s0

=

1. В

случае, когда

Т а б л и ц а

7

* i

X.,

*1

1

2

1

. , .

I

0

0

0

2

2

3

3

1

1

...

1

3

4

3

• • •

3

2

2

2

4

4

1

1

3

3

3

—

и s 0 = i .

Выберем

диагностическую

последовательность 2 =

0

и по процедуре П4 построим контрольную последовательность р

=

ми переходов состояний и выходов.

Средства

экспериментатора определяются возможностями

экс­

периментов:

приложениями входных последовательностей Pi,

Pi,...

pb и фиксированием соответствующих выходных

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

ностей

ди д2,

qk. Если полученное соответствие

между pt

и qt

при і =

1, k

не совместимо с законом функционирования автомата

А, то будем считать, что данный

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

исключает

автомат

А. Будем считать также,

что цели, к которым

стремится

деляются следующими задачами.

класс автоматов { Л ^ / ,

З а д а ч а

к о н т р о л я : задан

где / =

(1, 2,

п), и автомат А0. Требуется построить эксперимент,

каждый

вариант которого исключает

все автоматы Л,

при 7 £ I

и совместим с автоматом Л0 , или исключает автомат Л0 .

З а д а ч а

д и а г н о з а :

задан класс автоматов

{Л,-}^;. Требуется

построить

только одно / такое, что

данный вариант эксперимента исключает

все автоматы Ап

где і Ф

j и і £ I , и совместим с автоматом Л/.

2.1.

Правила

вывода

заключений

при

безусловном э к с п е р и м е н т е

Пусть задан класс

абстрактных

автоматов

{At}i£l

= {(Sh X,

Y, б , - Д ; ) Ь

.

(2.1)

из множества

с : Sh

где

— множество всех тех

состояний s,

для которых

\ (s, р) =

q. Таким образом, определяется семейство

множеств допустимых

начальных

состояний

совместимое

с реализацией

пары последовательностей (р, q). При

этом некото­

рые множества Si могут оказаться

пустыми.

ным, если

V W Y s £ S i V t £ S i З , (1, (5, р) Ф %І(t, р)).

(2.2)

докажем

его.

Лемма 2.1 .

V « V s e s , V j e

S /

3 p

(X, (s, p) ф

%j (s, p)) <-У

^pV^iYsQs.Vl£Sj(K(s,

P) Ф h(s,

P)).

Д о к а з а т е л ь с т в о .

Импликация влево следует из форму­

лы 3xVyP

(х, у)

V t f 3 x P

(х, у).

Докажем импликацию

вправо.

Пусть выполняется левая часть эквивалентности (2.3). Предпо­

ложим, что для каждого і £ I

St

=• {s [,

s'2, ....

sln.) и

/ =

{1, 2,...

N).

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

(s\, si) последовательность,

для

которой

X1 (s}, p(s\, s2)) ф A-2(sf, p(s{, s2)).

Чтобы

построить

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

ность p(s\, s2, si), на которой

состояние si отличается

от состояний

si и si,

достаточно

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

(s{, s2)

приписать

справа

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

61 (sJ, p(s\,

si))

и б2

(si,

р (si, sf)). Если

теперь

к

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

p(s\,s2,sl)

справа

приписать

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

на которой

различаются

состояния 6x (sl, p(sl, sf, si))

и

62(s|, p(s{, sf, si)),

то

получим

по­

следовательность p =

(sj, s2,

si, S3),

на которой состояние si

отлича­

ется

от

состояний

si,

s2 и

s|.

Так

строится

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

р (s\,s2\,

si,

si,),

на которой

состояние

s\ отличается от s\, s2, ...

s2..

Возможность аналогичных построений для каждого состояния

каждого автомата

показывает,

что

ЧІФІVses,

3 в Y - £ S . ( К (s, Р) Ф h(s,

Р)).

Последовательность р (s\, s\, s2,

si,

...

, s2ni),

на которой состояния s\

и s\ отличаются от состояний s2,

si,

... , s2ni,

можно построить, при­

писав к последовательности р (s\, s

,

s

, ...

,

s^)

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

2

2

t

на

которой

состояние

бх

(4, p(sl, s], s|,

. . . ,

s2n,)) отличается

от

состояний

s2,

si,

...

,

s2n„.

Так

строится

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

p(s\,

si,

...

,

s'„t, s], si,

...

,

s2n!), на которой состояния su s2

s„,

отличаются

от состояний s2,

si,

s~n,.

V W

Э р

Ys£S.

V I £ S

. (A* (s, р) Ф %, (s,

р)).

Обозначим

рц

=

р (sj, s'2,

sA., s{,

4,

si,).

Тогда

на

последо­

вательности

р =

р1 2 Різ ••• P\Npi3Pn

••• P2N ... PN—I, N

будет

отли­

чаться каждая пара

автоматов.

Лемма доказана.

Лемма 2.2. Пусть выделен некоторый

индекс

i0

£

I ,

который

равен

нулю.

Тогда

ViVflVses.

3 „ (\

(s, р) ф

Xt ( I р)) **

3

„ V M O V s e

s 0

V - S E S F

(Я0 (s,

р)

* A,,, (s, р)).

(2.4)

Лемма 2.2 является следствием леммы 2.1.

Введем

следующие

обозначения:

Sfx

= {s £ 5,1

Хс

(s, х) = у),

5AV =

U S

L

§X(S)*=U{

U

e,(s,

JC)),

(2.5)

ф (Si t Sx,

x\

...

xk,

y1...yk)

=

=

(6«_,(- •. (6,,(б„ (5?;) n

S*;) . . . )

n

S?*)).

(2.6)

Имеет место следующая теорема.

. Теорема

2.1.

Диагностическая

задача

для

класса

автоматов

(2.1)

решается с помощью входной последовательностир

— хгх2

... xk

тогда

и только тогда,

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

V,,... yk

3 , (Ф & ,

S

IX

l . . .

xk,

у,...ук)с

SJ.

(2.7)

Д о к а з а т е л ь с т в о .

Покажем,

что для

класса

абстракт­

дующему

соотношению:

3 . . . Х/г

V* ...

yk 3 , (Ф (6Х .

х х . . .

У і

. . . yk)

cz Sd.

(2.8)

Рассмотрим импликацию вправо. Пусть (2.8) не выполняется.

Это означает, что для любой входной последовательности

хг...хк

найдется такая выходная последовательность у^.-.уь,

что при

не­

которых і и

на равных между собой,

существуют s

£ 5 г и s £

Sj,

для которых

справедливо включение:

{5,

s)

cz ф(6д ,

Sx, хг

.. . xk,y1

... yk).

Из этого

включения

следует,

что

имеются

s,

£ Si и

Sj £ Sj

такие,

что Xt (sl7

xk)

= Xj (s^ xk) =

ykH

{sv

~sj) cz Ф (Sx,

Sx, xx ...

xk,

уг

... yk).