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

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

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

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

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

Добавлен: 30.06.2024

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

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

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

5/о cz 5,-, относительно

автомата А0 и множества 5 0 0 > если выпол­

няется (2.16).

 

Определениями 2.1

и 2.2 выделяются входные последователь­

ности, с приложением которых решаются диагностическая и конт­ рольная задачи.

Однако непосредственно в приложениях под тестом удобнее понимать такие входные последовательности вместе с перечислен­ ными возможными исходами эксперимента с указанием соответ­ ствующих результатов вывода.

2. 2. Правила вывода заключений при условном э к с п е р и м е н т е

Простому безусловному тесту соответствует безусловный экспери­ мент. Возможности безусловного эксперимента можно расширить переходом к условному эксперименту, в котором прикладываемая на 1-ом этапе часть входной последовательности определяется частью входной последовательности, прикладываемой на (I — 1)-ом этапе, и реакцией на нее. В этом случае исследователь влияет на процесс эксперимента. Схема действий при условном эксперименте следую­ щая:

1) прикладывается некоторая входная последовательность рг и фик­ сируется соответствующая выходная последовательность qx\

2)на основании анализа пары (pv qL) определяется последователь­ ность р2;

3)прикладывается входная последовательность р2 и фиксируется выходная последовательность q2 и т. д.

Формализация правил вывода в простом условном диагности­ ческом эксперименте осуществляется далее с помощью теоремы 2.4.

Предварительно докажем лемму. Лемма 2.3.

 

 

Ъл№£>

 

= 8,s (&,

(S£) П Sxi).

 

(2.17)

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

Пусть

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

правой

части

равенства (2.17). Тогда, пользуясь определениями

8x,Syx по

(2.5),

приходим

к выводу, что

принадлежность s правой

части эквива­

лентна:

 

 

 

s А з ,

 

 

 

 

 

 

 

3 , 3 A

(s', л-2) =

3 S A- (s", хг)

= s' А

(2.18)

 

А 3 Л

(s", X,) =

Й Д

э

л

(s\ А-2) =

у2.

 

 

 

 

Пусть s принадлежит левой части (2.17). Тогда

 

 

 

3 , 3 s -6, (s", хгх2)

=

s А

3 A

(s", * А ) =

уху2.

 

(2.19)

Из (2.19)

следует

(2.18)

на

основании импликации

З (Р /\ Q) - >

Э Р А

Э Q. Этим показано,

что

правая часть равенства

(2.17)

включает левую часть.

 

 

 

 

 

 

 

 

 

На основании

формулы

6 ( П « І )

С : П.^

(а*) получаем включение

 

 

 

 

і

 

 

/

"

 

•

 

4*

5Ї

правой части равенства (2.17) в левую часть, чем завершается доказательство.

Теорема 2.4. Диагностическая задача для класса автоматов (2.1) решается простым условным экспериментом тогда и только тогда, когда выполняется условие

3 p , V * • • • 3 p f t V w 3 , ( ( D ( 6 p , S I P l

... pk,qi

..

. qk)

cz

S,), (2.20)

где 5p, Sqp определяются для

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

no

(2.5).

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

Пусть

справедливо

(2.20).

Покажем

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

Для любой выходной последовательности qx найдется входная последовательность р2, которую можно выбрать для продолжения эксперимента.

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

ных последовательностей pv р2, ....

pk

таких, что для любого набора

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

q2,

qk

имеет место

Э£ (Ф(5р, S"p, рх ...

pktqx

...

qk) cz St)

на основании леммы 2.1. Это означает, что применением правил

вывода

(2.7) при анализе пары {рхр2... pk, qxq%-.'.qk) определяется

один и

только один автомат.

Пусть диагностическая задача решается простым условным экс­ периментом. Тогда можно выбрать входную последовательность рх и для любой выходной последовательности qx выбрать входную по­ следовательность р2 и т. д., выбрать входную последовательность pk, что для любой выходной последовательности qk оказывается, что только один автомат может реализовывать пару {рхр2... pk, qxq2...qk). Анализ этой пары можно осуществить с применением правил вы­ вода (2.7). Их формальная запись с учетом леммы 2.3 дает (2.20).

Следствие 2.3. Диагностическая задача может быть решена про­ стым условным экспериментом тогда и только тогда, когда она мо­ жет быть решена простым безусловным экспериментом. Очевидно, что если диагностическая задача решается безусловным эксперимен­ том, то она решается условным экспериментом. С другой стороны, из (2.7) следует (2.20).

Следствие 2.4. Диагностическая задача для класса автоматов (2.1) с множествами допустимых начальных состояний S«j a St решается простым условным экспериментом тогда и только тогда,

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

условие

 

 

Э р, V * . . . ЭPkV4k

Э , (Ф (бр, S$, P l ... pk,qi

... qk) cz St),

(2.21)

где бр, 5p определяются для последовательностей по (2.5) и (2.11).

Теорема 2.5. Пусть

задан класс автоматов (2.1).

Пусть

суще­

ствует такое целое k, что

 

 

 

 

 

 

 

V,/,... yk Э л-,... xk

3 , (Ф (6„

S'i,X

l ...

хк>Уі

...

ук)

cz St).

(2.22)

Тогда, в общем случае,

из (2.22)

не

следует

(2.7).

 

 

 

Д о к а з а т е л ь с т в о . Построим

пример,

противоречащий

импликации: (2.22)->-(2.7). Предположим, что / = { 1 , 2 }

и | Х.| = | Y\.

Для состояния s £ Sx функцию

6] s определим

так,

чтобы она

осу­

ществляла взаимнооднозначное

отображение

X на 5 j . Аналогично

поступаем с функцией *62S', где s' £ S2. Условие (2.22) будет выпол­ нено, если

Yx(K(s,

х)фХ2(5',х)).

 

Этому легко удовлетворить, если | X | > 2. На остальные

состояния

из множеств Sx и 5 2 никаких

ограничений не наложено,

и они, в

частности, могут составлять один класс эквивалентных состояний. Формализуем понятие простого условного диагностического

теста.

Определение 2.3. Семейство множеств входных последователь­ ностей (Я/},-£./, где J = {1, 2, k), будем называть простым услов­ ным диагностическим тестом для класса автоматов (2.1) относительно

семейства множеств допустимых начальных состояний {Sio}i£I(u),

е с л и

Sp.GP.Vui-iP. і •••

3 Р / і Є р Л У | 1 7 л і = ірй |Зг (ф(бр, S% рх ...

...

pk,qt ... qk)cz S,).

(2.23)

Перейдем к решению задачи контроля. В этом случае анализ пары (р, q) также связан с определением множеств S4pn80 (Sp). Имеет место такая теорема.

Теорема 2.6. Задача контроля для класса автоматов (2.1) отно­ сительно автомата А0 = (50 , X, Y, б0 , Я,0) решается простым услов­ ным экспериментом тогда и только тогда, когда выполняется ус­ ловие

3

Р, V|

і = і Р і 1 3 pl{ Y\qk і = | pk і (Ф (бр, S4P, рх ...

pk, qx .. • (2.24)

...

qk)

cz S0 V Ф (6P > S$, P l ... P k , Q l ... 4k) П S0 =

0 ) .

Теорема 2.6 является очевидным следствием теорем 2.3, 2.5. Следствие 2.5. Задача контроля для класса автоматов (2.1) с мно­

жествами допустимых начальных состояний 5,о CZ Sit относительно автомата А0 = (S0, X, Y, б„, Х0) и множества 5 0 0 , решается простым условным экспериментом тогда и только тогда, когда выполняется условие

З Р . У Н . ^ І Р . | 3 P f c V i <ik\ = \pk і (ФФР, Sqp, P l . . .

qx . . .

qk)czS0\/

V Ф (бр, S% Рг ...

P k , q i ... qk) 0 S0 = 0 ) .

(2.25)

Определение 2.4. Семейство множеств входных последователь­

ностей {Pj}j£j, где / =

{1, 2 , f t } , будем называть простым услов­

ным контрольным тестом для класса автоматов

(2.1) с множествами

допустимых

начальных

состояний SJO с : S£

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

^о — (^о, X,

Y, б0 , Х0)

и множества S0 0 с

S0 ,

если выполняется

условие (2.25) при р,- £ Pj, j £ J .

2. 3. Устойчивость установочных экспериментов

В работе [16] дана классификация экспериментов: безусловные и ус­ ловные, простые и кратные, диагностические и установочные.

Установочным является эксперимент, который решает следую­ щую установочную задачу: известно, что данный автомат Л, таблица

переходов и выходов которого имеется в распоряжении

исследова­

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

из состояний Si,,

s,„,

si

.

Требуется

установить автомат А в

известное состояние. Очевидно,

что уста­

новочный эксперимент решает задачу диагноза.

В этом

случае

каждый автомат из анализируемого класса

{A^tqj

рассматривает­

ся как изолированный

подавтомат автомата Д (Л1 т

Л2 ,

Aj).

На эксперименты можно наложить новые ограничения и продол­ жить их классификацию.

Виды ограничений могут быть связаны с возникающими иногда

трудностями

реализации

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

 

 

Пусть известно,

что исследуемый автомат

является

автоматом

Л = (S, X,

Y, б, X) в некотором состоянии из множества

состояний

S0czS.

 

 

 

 

 

Предположим, что последовательность р = xix.2...xk

является

установочной, т. е.

после

приложения этой

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

к автомату А и наблюдения соответствующей

выходной

последова­

тельности определяется конечное (заключительное) состояние ав­ томата.

Пусть автомат Л является математической моделью некоторого реального устройства R. Приложению входной последовательности р к автомату Л соответствует осуществление некоторой кодирован­

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

устройство R.

При этом устройство выдает последовательность

реакций, которая

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

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

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

реакций реаль­

ного устройства R (или кодирование ее символами из 10 проведено неправильно, то возникает необходимость решать следующую зада­ чу: известно, что исследуемый автомат является автоматом Л в со­ стоянии из множества состояний б р (50 ); требуется установить Л в известное состояние. Эта задача отлична от исходной установоч­ ной задачи только множеством начальных допустимых состояний. Но этого достаточно, чтобы в общем случае решать задачу заново,

т. е. находить другую входную установочную

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

и составлять другую схему возможных исходов

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

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

Рассмотрим простейшие свойства таких экспериментов. Обо­ значим:

Р (S) — множество всех подмножеств множества S; Xі (Y1) — г-я декартова степень множества X (Y).

Для автомата А определим отображение Tt:

 

TC:P(S)

XXі

х

Yl^P(S)

 

следующим

образом:

 

 

 

 

 

 

((S0 , х1

х(,

Уі ••• У,),

£ Ті

(2.26)

 

«-» ф (б,., Si,

хг

...

хс, yj_ ...

уд =

 

SL.

Пусть Т=

U Г,..

 

 

 

 

 

Определение 2.5. Входная последовательность р называется' ус­ тойчивой относительно множества состояний S 0 c S автомата А, если

V| , і = і р і (Т (6, (S0 ), p,q)^T (S0, р, q)). (2.27)

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

Так, для автомата Alt заданного табл. 8, не существует устой­ чивой установочной последовательности относительно множества

допустимых

начальных

состояний

 

 

 

 

Т а б л и ц а

8

Однако

в

ряде

случаев

уста­

 

 

Ч

ч

Ч

ч

новочная задача для автомата А,

S

\

 

 

 

 

для которого

не существует

устой­

h

 

s2

 

Уі

Уі

чивой установояной

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

 

 

 

 

 

ности, сводится к такой

установоч­

s2

 

S3

 

Уі

Уі

ной задаче для автомата А,

когда

 

 

 

 

 

 

 

 

для него устойчивая

установочная

S3

 

Ч

S l

Уі

Уі

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

может

быть

s4

 

 

s4

 

 

найдена. Например,

для

автомата

 

ч

У2

Уі

Аг

устойчивой установочной

по­

 

 

 

следовательностью относительно множеств ЪХг (50 ) и 8XlXl

(S0) яв­

ляется входной сигнал хг. Для автомата Аг

можно свести установоч­

ную задачу для множества S0 к установочной задаче для множества

§х,

(So) приложением входного

сигнала

xz.

 

 

Очевидно, что входная последовательность Р является устано­

вочной относительно множества S0czS

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

 

V i , , = | P l ( | T , ( S 0 , p , ( 7

) | < l ) .

(2.28)

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