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

1.6.

Контрольный э к с п е р и м е н т

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

Автомат Л = (S, X , Y, 6, X) будем называть однородно-диагностируе­

мым,

если для любого х £ X

найдется такое целое

I, зависящее

от х,

что хс есть диагностическая последовательность

для автома­

та Л.

Пусть задан сильносвязный

однородно-диагностируемый авто­

а объединение их равно X . Обозначим через / разбиение

множества

X , содержащее

один класс, а

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

разбиение

множества X , в

каждом классе

которого содержится

ровно один

X =

w (Ф¥)

х = го(Ф) Л х 3= w

Пусть х

Ф w (Ф). Через Ф (х, w) обозначим разбиение множества

X ,

полученное

из

разбиения Ф

объединением

в один

класс двух

классов, содержащих х и w соответственно.

Пусть X

= {xlt

хт)

и для

всех і,

1 •< і

<: in, х1'

— диагно­

стическая последовательность для автомата А. Для всех

х £ X по­

ложим, что

Т^х — S. Для

всех

s £ S

положим,

что

Ф° =

О,

где

Ф5 — разбиение множества

X . Пусть также Ф' =

Пф£,

где П

—

знак умножения разбиений.

s

Процедура П5.

1. 0-й ш а г .

Полагаем,

что

р = е.

К

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

р

справа

приписываем

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

х\1+к,

где

k — наимень­

шее

целое,

для

которого

найдется

такое

целое h,

что

h <

k

и

6 (s0 , Xi) =

б (s0 , Хі). Удаляем из множества Txt

состояния

б (s0 , я?),

где

0 < : h -< k,

и .полученное множество

обозначаем

через TlXl.

Полагаем,

что

/ =

1, Р/-і

= *ї + / *

и

sy- =

б (s„,

pj).

Переходим

к п.

2.

2. /-й ш а г .

Если ф , " 1 Ф I,

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

q,- =

е,

и

пере­

ходим

к п. З, в противном

случае

проверяем, выполняется

ли ра­

венство

ф ' — 1 =

/ . Если оно

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

то построение

последо-

вательности

окончено,

в противном случае находим кратчайшую

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

qlt

для которой ф^ - 1

Ф I,

где s = б (s/,

q{).

Переходим к п. 3.

3.

К последовательности p/ _ i приписываем справа последователь­

ность

<7/. Пусть

г (p/_i<7/) = х, где г (р) — последний

символ из X

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

р. Находим наименьшее і, 1 <; і

<: т, для

ко­

торого

х Ф

хс

(ФІ- 1 )-

Полагаем, что Ф£ =

ФГ"1

(х, xt).

Для

всех

t Ф

s,

полагаем, что ФІ = Ф'Г1.

К

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

Находим наименьшее і, дня

которого

XtX/(0s);

вычисляем

находим xpamwuu/eeq, Ш

I

которого

ff ls.nl *1

Л

I'If

Ю р:=рд І х•• =Hpqy, s• =&(s, у)

Коней

Рис. 6. Блок-схема процедуры П5.

Р\-\Ц\ приписываем справа последовательность

x t

+ 1

н обознача­

ем полученную последовательность через р/. Здесь

k — наимень­

шее целое, для которого б (s, JC?) $

Т'х~1 или найдется такое целое h,

что h < k и б (s, xt)

= б (s, *?). Полагаем, что Т{. =

7 ^ '

— (б (s,

0 < : h < : fe. Для всех х,

х Ф Х[,

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

Т'х

=

Тх~1. Уве­

личиваем значение / на единицу,

полагая, что s;- =

б (s0 , p/ _ i), и

переходим к п. 2.

Блок-схема процедуры П5 представлена на рис. 6. В блок-схеме

опущен индекс / в обозначении множеств Т'х и Фу.

Покажем, что всякая,

построенная по П5 последовательность,

на Г меньше числа классов разбиения ФІ

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

чтобы на некотором /-м шаге выполнялось равенство ф'$ =

/, требует­

ся ровно т — 1 шагов процедуры. Поскольку

в автомате А ровно

п состояний, то в процедуре П5 должно быть ровно

(т — 1) п +

1

шагов.

Теперь покажем, что на любом /-мшаге процедуры, / >- 1, всегда

найдется транслирующая

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

ft

и ее длина не

пре­

восходит

mУ _—j

j - Очевидно,что ft = е.

Как

было показано

выше,

требуется

ровно т — 1 шагов для того, чтобы число классов

неко­

торого разбиения Os уменьшить до 1. Следовательно, на /-м

шаге,

/ > - 1, найдется не более

состояний s, для которых выполня­

ется

равенство

ф'$ = / .

Поскольку

автомат

сильносвязный,

то

п р и ф ' - 1 ФI

всегда найдется последовательность, переводящая авто­

мат А

в состояние t, для которого ф / - 1

Ф I . Учитывая, что на /-м

шаге существует не более \

j состояний, для которых ф{~1

=

/,

получаем, что длина ft не превосходит

Г і -

1 1

ут_у

Пусть

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

П5,

р,- - < р,

и

р,- — построена

на /-м шаге

процедуры. Из

описания

процедуры

следует,

что

s (J Т),

если

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

р 1 (

для которой

рг

Xі < . pj,

s =

б (s0 , рх ),

И если х

— xit

то I =

/г . От­

сюда вытекает, что для всех / имеет место соотношение

p J = i f t X < P / - ^ s

$

Т'х,

(1.17)

r{pl_1gi)

=

x-^s

(£

ТІ.

(1.18)

Пусть г (py _ift)

=

х.

Пусть

на

/-м шаге

ft =

е.

Тогда

P / - i f t

=

= p; -_2ft_i^f t +',

где

£ — наименьшее

целое,

для

которого

или

6 (s0 , p ; - _ 2 f t _ i ^ )

$

Т і - 2 , или б

(s0 , pj^2qi~xxk)

= 6 (s0 ,

p;_2ftLix'! )

для некоторого /г <

ft. В первом случае

s $

Г І - 2 , во втором случае s

удаляется из Т!Г'

на

(/—1)-м шаге. Следовательно, если ft

=

<?,

то (1.18) выполняется. Поскольку для

/ =

1 ft

=

<?, то

(1.18)

для

смотрим случай

qj-фе.

Пусть

p / _ i f t = р'х,

для

некоторого

р',

и 6 (s0 , р') = t. Из описания процедуры П5 следует,

что Ф|~' =

/ .

Тогда

найдется

такой h-й шаг,

/г <

/, что или г (pA _ift,) = л:, или

P/,^ift,x - < рЛ . В

первом случае

по

предположению

индукции і (£

(£

, во втором по соотношению (1.17) t

Г І - 1 -

Очевидно,

что

если t (£ Т1 *- 1 ,

то s =

б (t; х) (£

T'i- Следовательно, соотношение

(1,18) для случая / = Д а значит, и для всех /, выполняется.

Поскольку для любого s ф 5

=

О и Ф( /"~ ' "

=

/ , то для

каждого

перехода (s, х) найдется такой шаг /процедуры,

что или

Pi—\qjX

<.

^

Pi,

или г (pj-iqi)

= х,

где s =

б (s0 ,

pi-iqi).

Тогда по

(1.17) —

(1.18)

s І

ТІ

и,

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

у

r f - " " =

0 .

Используя рассмотренные свойства процедуры П5, докажем сле­

дующую

теорему.

Теорема

1.9.

Любая

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

построенная

по про­

цедуре

П5,

является контрольной

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

для ав­

томата

А.

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

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

по

П5. Пусть

А'

=

(S', X,

Y,

б', X') —

произвольный

автомат,

у которого \ S' | •< п, и b £ S' — произвольное начальное

состояние

автомата

А'. Нужно

показать,

что X (s0 , р) =

X' (b,

р) ->

А

—

А'.

Пусть

X (s0,

р)

=

X' (Ь, р). Поскольку

[]Т(хт~1)п

= 0 , то для всех

х

і,

1 < : і <1 т,

существует взаимно

однозначное

отображение

ф/

множества 5

на 5', задаваемое

формулой

ф,- (s) =

d <-> X (s, х*1) —

=

X' (d, *'*)• Из описания

процедуры

(см. блоки

2 — 4

блок-схе­

мы на рис. 6) следует,

что

для

фг

выполняется

соотношение

ф, (б (s,

Xt)) =

б' (ф, (s),

X,) Л ^ (S,

Х[) =

X' (ф, (s), x f ) . Для

того

чтобы показать равенство

А =

А'

и тем самым

доказать

теорему,

достаточно показать, что для всех і, /г, 1 < ; i,

h < ; m, ф,- =

фЛ .

Индукцией

по

/

докажем

соотношение

х,

=

л-Л (ф() -»- фг

(s) =

фл

(s).

(1.19)

Пусть

/ =

1 и

рх

= д : ? 1

+ ' ' Х 2 г +

' ' ,

где

р/ —

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

последовательности р, построенная на /-м шаге. Из описания

проце­

дуры

следует,

что

найдется

такое

целое

fx,

что

б (s0,

x\l+kl)

=

=

б (s0 , x\1+fl)

=

s для

некоторого

s £ S.

Поскольку

X (s0 , p) =

= X'(b , p) и последовательность

Xi'—диагностическая

для

А,

то

б' (ф! (s0 ), хі, + *1 )

=

б' (ф (s0 ), ^ I +

f l )

=

ф! (s) =

y2(s).

На первом

шаге существует только одна пара

(Xj, х2 )

входных

сигналов,

для

которой хг

Ф х 2

и хх

=

х 2 (Фз).

Следовательно,

для

/ =

1

соотношение

(1.19)

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

Пусть для всех /,

1 < ; / < ; q — 1, соотношение

(1.19) выполняется.

Пусть

/

=

g,

pj =

p j - x q j X l ' +

k i ,

s

=

б (s„,

P/_i?y)

и

t =

б (s0 ,

где

р'л;Л

=

pj-iqj.

Покажем,

что для (xh,

xt)

соотношение

(1.19)

выполняется. Из

описания

процедуры

следует,

что

ф,, (б (s0 , р')) =

б' (Ь,

р'),

тогда

Фа (s) = фй

(б (s0 , р'хЛ ))

=

б' (фЛ

(б (s0 , р')), х„) =

б' (6,

p'xh).

Из

определения отображения ф; имеем:

ф„ (s) =

б' (Ь, р'х^) =

ф£

(s).

Следовательно, для (xh,

х()

соотношение (1.19) выполняется. Напом­

ним, что Ф'$

= Ф І - 1

(xh, xt).

Пусть

Кь

и

/С,- — классы

разбиения

ФІ~\

содержащие

элементы

xh

и

xt

соответственно. По

предгіо-