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

Последовательность z £ X*

называется диагностической для ав­

томата А, если для всех s, t £ S выполняется К (s, z) =

К (t, z) ->•

- > s = t. Автомат А

называется диагностируемым [66], если для него

существует диагностическая

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

В дальнейшем предполагается, что исправный автомат является

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

последо­

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

Пусть s0 — фиксированное начальное состояние исправного ав­

томата.

Последовательность р £ X*

будем

называть

Определение 1.1.

контрольной для

автомата

А (относительно

заданного класса

= (5', X, Y, б', %') и всех

t (Е 5'

выполняется

соотношение

X(s0, p) =

r(t,

р)-+А = А',

(1.1)

автомату

и он отреагировал на нее так же, как исправный, то иссле­

дуемый

автомат

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

исправному.

На

множестве X*

введем

отношение

>

следующим

образом:

р >• q,

если

р =

qw для

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

w £ Х*\

р <; q, если р

<

q и р Ф

q. Если р <

q,

то

р называется

началь­

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

q. Разностью

р — q

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

р

и

q,

для

которых

q <

р,

назовем

такую последовательность до, что qw =

р.

Переходом из состояния

s £ 5

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

ти до Є X*

назовем пару (s, до). На множестве всех переходов автома­

та А определим частичные операции сложения и вычитания:

(s,

p ) +

{t,q)

=

р - ^ ) > е с

л и

6

=

[ не

определено

в

противном

случае;

(s

р) — (t

<7) =

( ( 6 ( S

' ^

Р ~ q ) '

Є

С Л И

q < P

H S

=

'*

\не

определено

в

противном

случае.

условиями:

У 1 .

(s, до) Є Zx (р) тогда и только

тогда, когда существует после­

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

рг,

для

которой ргг <

р, pjwz

<

р

и б (s0 , рх ) =

s.

Полагаем, что

Zj (р)

s

Z (р);

У2.

если

(s,

до),

(/,

q) £ Z (р)

и

(s, до)

+

(/,

q)

=

(v,

г),

то

(»,

г)

Є Z (р);

(s,

до),

<?) € Z (р)

и

(s, до) — ( t

то

УЗ.

если

q)

=

(v,

г),

(v,

г) Є Z (р).

Полагаем, что никаких других переходов в Z (р) нет.

Покажем вначале, что (1.4) выполняется для всех (5, w)

£ Z±

(р).

Пусть

(s, w) £ Z x

(p),

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

р х ,

для

которой р х z <4 р,

pxtt)z < р, б (s0 , pi) = s. Для

случая w = е из

(1.3) непосредственно

вытекает (1.4). Пусть z <

wz. По (1.2) Я- (s0 ,

pxwz)

= ?і/ (f, pxwz),

a no (1.3) ф (6 (s, ay)) =

б'

(£, pxw)

и

ф (s) =

= б' (if, Pi). Используя последние равенства,

получаем, что ф (б (s,

до)) =

б (ф (s), tw). Из равенства

(1.2) следует вторая

часть соотно­

шения

(1.4) и, значит, для (s, ш)

соотношение

(1.4)

имеет место.

Пусть теперь (s, ft), (б (s, ft),

ft) £ Z (p)

и для этих

переходов

Ф (б (s,

ftft))

= ф (б

(6 (в,

ft), ft))

=

б'

(ф (б (s,

ft)),

ft) =

б'

(ф (s),

ft ft). Вторая

часть

соотношения

(1.4)

следует

из

того,

что

(1.4)

справедливо

(s, ft)

и

(б (s,

ft), ft).

Таким образом, для

перехода

(s, ft ft)

соотношение

(1.4)

имеет

место.

Аналогично

показывается, что если соотношение (1.4) выполня­

ется для (s ft),

(s, ft)

€ Z (p) и ft

< ft, то оно выполняется и для

разности (б (s, ft), ft

— ft) этих переходов.

Таким образом, показано, что

соотношение (1.4) справедливо

/ >

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

р\. Кроме последовательностей

на каждом /-м шаге (j >• 1)

этого процесса вычисляются вспомога­

тельные множества ТІ- s

S,

где г £

R = XU{e). В начале процеду­

ры

для каждого г £ R

множества

задаются, причем Т°е = S.

У5.

На

у'-м

шаге

процедуры

строится

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

Pi = Pi-iQ/Пг,

где р]—\ — последовательность,

построенная на предыдущем шаге,

г/ — некоторый элемент из R, а

qs

— такая последовательность, что

выполняется

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

для всех

д ' и х

q'x <

q

б (s0 l

pj-iq')

£ T°x—

i t 1 .

Множество Tr~l

— множество

состояний

автомата А,

построенное

на (/ — 1)-м шаге процедуры.

У6. На /-м

шаге

(1 - < /) для всех х

£ X

строится

множество

Vic

по

правилу:

s £ V'x,

если

существует

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

рг,

для которой p-yXz

=

pj

и б (s0 , р2 ) =

s. Кроме того, строится мно­

жество V'e по правилу: s £

V'e,

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

рх,

для

которой

рггг

= р,- и б (s0 ,

рг)

— s. Затем, для

всех г £ R

строится множество ТІ, равное T'~l

—

V'r.

У7.

Процедура

имеет. конечное число

шагов. На

последнем,

с-м, шаге процедуры для всех г £ R множество Т°г пусто.

Если s £ V'r,

то будем говорить, что состояние s удаляется из

множества Т°г на /-м шаге процедуры.

Класс всех

процедур,

удовлетворяющих

условиям

У4—У7,

су К, так так с помощью этих процедур строятся

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

ности, для которых не выполняется равенство pj =

pj_iq,rjZ.

Найдем условия, при которых с помощью процедуры из класса

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

контролирующие все

переходы

автомата А.

Пусть

Z ° = ( (J Т°х

х

{x})UT°ex{z).

Теорема

1.2.

Любая последовательность,

построенная

с по­

мощью произвольной процедуры

из класса К, контролирует все пере­

ходы автомата А

из множества Z°.

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

Пусть

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

постро­

Поскольку на последнем, с-м, шаге процедуры Т°е =

0 ,

то для каж­

дого s £ S найдется такое рг,

что рхгг<С р и б

(s0 , p j =

s. Следова­

тельно, по У1 7^ х

{z} g Z j

(р). Для всех /, 1 <

/ < с , найдется'та­

кая последовательность рх (зависящая от / ) , для которой

p^zqjTjZ

<;

<

р. Тогда, полагая б (s0 , р^ =

s и используя

У1, получаем,

что

(s,

zqjrj)

£ Z i (р). Поскольку (s,

z) £ Zr (p),

то,

используя УЗ,

по­

лучим, что для всех / (tj,

qjri)

£ Z (р).

Здесь

tj =

б (s0, p/_i).

Индукцией

по

/

покажем,

что

(fy, q/) £ Z (р).

Из условия

У5

следует,

что

qx

=

е.

Тогда,

поскольку (tj,

z) £ Zx

(р),

получаем,