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

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

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

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

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

Добавлен: 30.06.2024

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

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

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

 

Рассмотрим

примеры,.показывающие

достижимость

полученной

верхней

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

построенной

по мини^

мальной процедуре. Пусть автомат А2 задан табл. 2 и для него z

=

= х2х1,

V =

{1, 2, 3, 4}. При таком

V автомат Ау2 сильносвязный

и, значит, имеет правильную нумерацию слоев. Пусть s„ =

1.

 

 

 

Для

случая

т — 2, хх =

О, х2 =

1 полагаем Те =

Тг

= {1, 2,

3, 4}, то Т0

=

0

 

и по процедуре П2 (блок-схема П2 представлена

на рис.3) строится

последовательность р — z 2 l z l l z 2 l l l z 2 l l l l z 2

дли­

ны 28. Верхняя оценка из (1.11) также равна 28 и,

значит,

до­

стижима. Легко

видеть,

что

верхняя оценка из (1.11)

достижима

для

любого

m >- 2.

 

 

 

 

 

Т а б л и ц а

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ч

 

 

х2

 

хт

 

 

*2

хт

 

 

 

 

 

 

1

 

1

 

 

2

 

2

0

 

0

0

 

 

 

 

 

 

2

 

2

 

 

3

 

3

0

 

1

0

 

 

 

 

 

 

3

 

3

 

 

1

 

1

1

 

0

0

 

 

 

V

Пусть автомат

ЛЗ задан

табл. 3

и для

него z = ххх2,

а0

=

1,

=

(1, 2, 3}. Для такого V автомат АуЗ

сильносвязный и в случае

m

=

2, хг =

0, х2

=

0

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

=

=

z2 0z2 0z2 0z длины

17.

Нижняя оценка

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

р

из

(1.6) также равна

17 и, следовательно, достижима.

 

 

 

 

 

Легко видеть, что для этого автомата оценка из (1.6) достижима

для произвольного а0 и всех т > 2.

 

 

 

 

 

 

 

 

Верхняя оценка из (1.11) длины последовательности, построен­

ной по произвольной минимальной процедуре из класса К,

по край­

ней мере на (я —

1)L короче верхних оценок для процедур

из работ

[58,

61, 64]

(см.

(8)

и (9)).

 

 

 

 

 

 

 

 

1.5.

Контрольный

э к с п е р и м е н т

с автоматом,

 

 

 

 

имеющим периодические

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

 

 

 

 

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

 

 

 

 

 

 

 

 

 

В предыдущих разделах при изучении свойств процедур построения контрольных последовательностей для автомата А (относительно заданного класса неисправностей) структура диагностической по­ следовательности z не учитывалась. В данном разделе рассматри­ вается автомат А, который имеет периодическую диагностическую последовательность z, т. е. z = vl для некоторых v £ X* и цело­ го /. Изучаются процедуры построения контрольной последовательно­ сти для автомата Л, зависящие от периодичности последовательно­ сти z. Показывается, что при / > 1 существуют процедуры построения контрольных последовательностей, для которых оценки длины ко­

роче оценок в неравенствах (1.6)

и

(1.11).

 

 

Пусть задан

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

автомат А = (S, X, Y,

б, X), для

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

z

=

Vі является

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

Пусть для всех г

£ R заданы

Т° по

правилу: если

г Ф wr

то Т°Г =

3

2—1686

33

= 5, в противном случае Тт = 5 — V, где V = pxw, w £ X и V — заданное множество, для которого V s 6 (5, р^. В разделе 1.3 с по­ мощью условий У4 — У7 определялся класс К процедур построения входных последовательностей по заданным Т°г и автомату А. Обо­ значим через /Сп класс таких процедур построения входных последо­ вательностей, для которых выполняются условия У'4, У'5, У'6, У'7.

У'4. На 0-м шаге

процедуры

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

равная

v.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

У'5. На /-м шаге процедуры, 1 <

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

pj = p / _ i

qjTjV,

где

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

построенная

на

предыдущем шаге, г;- £

R, а для

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

<7/ выполня­

ется соотношение: для

всех q'

и х

 

 

 

 

 

 

 

 

 

 

q'x<щ

 

б(s0 ,

/>/_,</') £Т°Х-

Т!~\

 

 

 

где Т!х~1 — множество

состояний

автомата

А,

определенное на

предыдущем шаге процедуры.

 

 

 

 

 

 

 

 

 

У'6. На /-м шаге процедуры для всех

х g X строится множество

V'x по правилу: s (Е V'x,

если существует

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

р',

для которой б (s0 , pj) =

s и рх л:#

=

р;-.

Кроме того,

строится мно­

жество

V'e по

правилу:

s £ V'e,

если существует

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

ность рг,

для которой б (s0 , р^) =

s и р ! ^ 1 =

pj.

Далее

полагаем,

что Т'г =

Т'Г1

— Vl

для

всех

г.

 

 

 

 

 

 

 

 

Очевидно, что при / =

1 условия У'4 — У'6 совпадают с усло­

виями У4 — У6 раздела 3.

 

 

 

 

 

 

 

 

 

Пусть

Z°n =

| Ц ^ х

 

U 7ІХ

{о).

Напомним,

что

Z (р) —

множество переходов автомата А, которые контролируются по­ следовательностью р. Множество Z (р) определено правилами У1 — УЗ раздела 2.

Легко показать, что имеет место следующая теорема, аналогич­ ная теореме 1.3.

Теорема 1.8. Любая последовательность р, построенная по произвольной процедуре из К„, такова, что

Z ° = Z ( p ) .

Процедуру из Кп назовем процедурой, покрывающей множество V, если множество Z° порождает с помощью операций сложения и вы­

читания переходов все множество 5

X X*. Аналогично разделу

1.2

обозначим процедуру П из Кп, покрывающую множество V, через

П (V). Очевидно, что всякая последовательность, построенная

по

произвольной процедуре П (V) из Kv,

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

вательностью для автомата А (сравните со следствием 1.2).

 

Опишем одну процедуру из /Сп и

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

ностей, построенных по этой процедуре. Для простоты описания получаем, что X = .{0, 1} и что Т° = S для всех г £ R.

Процедура ПЗ. Блок-схема процедуры приведена на рис. 4.. Работа всех блоков, кроме блока 6, ясна из блок-схемы. В блоке 6 строится кратчайшая последовательность q, для которой выполня­

ется условие б (s, а) €

U Тх и условие

У'5

описания

класса

АГП-

 

 

 

 

 

 

 

X

 

 

 

 

 

 

 

 

 

 

 

 

Заметим, что здесь

Тх

— текущее значение

 

множества

Тх

и Т =

=

М Тг.

Идея процедуры

ПЗ состоит

 

1'

Р

 

 

 

 

в

r£R

 

 

 

 

 

 

 

 

 

 

 

 

 

 

следующем:

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

 

2

 

*

 

 

 

 

 

1.

Строится

 

Р'•рг; 7~е>'Ъ-{s};y-=d(s,y)

 

іУЧ-^

где

k — наименьшее целое, для

 

 

 

 

 

 

 

 

которого

б (s0 ,

xfi)

не

принадлежит

 

 

 

 

 

 

 

 

текущему

значению

множества

 

Те.

 

 

 

 

 

 

 

 

 

 

2.

К

полученной

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

 

 

 

 

 

 

 

 

ности

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

справа

после­

 

 

 

 

 

 

 

 

довательность xvk+l,

где к — опреде­

 

 

 

 

 

 

 

 

лено выше и полученная ранее после­

 

 

 

 

 

 

 

 

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

переводит

автомат

А

 

 

 

нет.

 

\п Конец

 

из

состояния s0 в состояние, принад­

 

 

 

 

1

 

 

 

 

 

 

 

лежащее

Тх.

 

 

 

 

 

 

 

 

П? Находім кратчайшееqip'-pqwtifaq)

 

3. Если нужно, строится трансли­

 

 

 

 

 

 

 

 

рующая последовательность q и при­

 

 

 

 

 

 

 

 

писывается справа к ранее получен­

 

 

 

 

 

 

 

 

ной. Если

Т Ф 0 ,

то

возвращаемся

 

 

 

 

 

 

 

 

к

п.2.

 

 

автомат

сильносвязен,

 

И

 

h--"Tx-{s];p,=pxis:*6(sJ)

то

Поскольку

 

 

 

 

 

 

 

 

всегда

 

найдется

транслирующая

 

Рис.

4. Блок-схема процедуры

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

q,

которая

стро­

 

ПЗ.

 

 

 

 

 

 

ится

в

блоке

6.

Это значит,

что

шагов

строит контрольную

процедура

ПЗ

за

конечное

число

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

При

этом

следует

отметить

одну

особен­

ность

процедуры ПЗ: если

на

/-м

шаге

процедуры

Л/ Ф е,

то

б (s0 , Pi-xqi)

€

Т'Г1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Оценим длину последовательностей, построенных по процедуре

ПЗ. Пусть

J =

{/і,

 

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

номеров

шагов

процедуры, на которых найдется х € X

и состояние s £ S.,

удаля­

емое из Т° на этом шаге. Очевидно, что g

— mn.

 

 

 

 

 

Положим, что если h <z

і, то / Л

<

j t .

Нулевым ходом процедуры

назовем часть

процедуры

от нулевого

до

Д шага;

i-u

ходом

про­

цедуры назовем часть процедуры от /,-годо /j+i-го шага. Индукцией

по і легко показать, что сумма

длин всех

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

в процедуре ПЗ не превосходит

величины

 

mn

п

 

=т£(А-1)

=

В конце каждого хода к последовательности, построенной ранее, приписывается справа последовательность vl (см. блок 4), и таких ходов тп + 1. Непосредственно перед удалением состояния s из

3*

35

Те (см. блок 2) к последовательности, построенной ранее, приписы­ вается справа последовательность и, и блок 2 работает ровно п раз. На каждом ненулевом ходе процедуры к последовательности, по­ строенной ранее, приписывается х. Следовательно, длина постро­ енной последовательности не превосходит

 

 

 

тп+ {{тп +

l ) l +

n)-!j-+

" т ( " 2 ~ 1

}

 

 

(1.13)

и не короче

;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

тп +

((тп +

1) I +

п) -if-.

 

 

 

 

 

(1.14)

При

/ =

1

процедура

ПЗ

является

минимальной

процедурой

из К и оценки

(1.13), (1.14)

совпадают с

оценками

из

неравенств

 

 

 

 

 

 

(1.12)

и

 

(1.6)

 

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

 

 

 

 

 

 

В случае

/ >

1 оценка (1.13) коро­

 

LT0-^T0-{s};S--f(sJ)

 

 

че оценки из

(1.12)

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

\2\ р-.-рО:

 

 

оценка (1.14) короче оценки из (1.6))

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

L

 

 

 

 

 

 

на величину, равную п (І — 1) •

 

 

 

 

 

 

Таким образом,

учитывая пери­

 

 

Нет

 

 

одичность

 

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

z,

 

J L

 

 

 

 

 

 

 

 

можно построить процедуру с

более

 

Т

 

 

 

 

короткими

 

оценками

длины,

чем

 

 

 

 

 

оценки в (1.12) и (1.6).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Для

случая

/ =

L z =

х1

 

(для

нет

 

 

 

 

 

некоторого х)

и процедуру ПЗ легко

 

 

 

 

 

переделать

так,

чтобы

понизить

Находим q; P"pff;S:=tP(s,0

 

 

оценки

(1.13) и (1.14). Для случая

 

І •

 

 

 

 

 

 

 

z — х1

из

 

условия

У'6

следует,

 

 

 

 

 

 

что на всех шагах произвольной

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

П4.

 

процедуры

 

из Кп

ТІ

~

Т[.

Сле­

 

 

 

 

 

 

довательно,

 

можно не

задавать

отдельно множества Г° и не учитывать его при построении последо­ вательности р. Но это равносильно построению последовательности по ПЗ для автомата, у которого входной алфавит состоит из (т — 1) элементов, т. е. в процедуре будет ((т — 1) /г + 1) ходов. Учитывая сказанное, для случая X — {0, 1} и z — 0 і удаляем блоки 7 и 5 из блок-схемы процедуры ПЗ и получаем процедуру П4, блок-схема которой представлена на рис. 5.

Оценим длину последовательности р, построенной по П4. В конце каждого хода процедуры к последовательности, построенной ранее, приписывается 0L и таких ходов ((т — 1) n -f- 1). В автомате тп переходов, которые контролирует последовательность р. На t'-м ходе к последовательности, построенной ранее, приписывается сло-

во <7/. длины, не превышающей величину

І — 1 "

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

1

d (p) не превосходит

величины

 

 

 

 

 

 

 

 

 

 

mn +

((m-l)n+\)L+

 

 

( " ' - ' ) « ( " - » )

(1.15)

и не короче

 

 

тп +

((т — 1)п +

l ) L ,

 

 

 

(1.16)

где

 

 

 

 

 

 

 

 

 

 

 

 

 

(Ш—1) U

 

 

 

 

 

 

 

 

(/Я — І)я(я — 1) _

 

 

 

 

 

 

 

 

 

 

^

і — 1

 

 

 

 

 

 

 

 

2

 

 

 

 

от — 1

*

 

 

При L — I оценка

(1.15)

((1.16))

короче оценки

(1.13) ((1.14)) на

величину (п +

1) L +

"

^

.

 

 

 

 

 

 

 

 

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

и (1.16).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пусть

автомат

А4

задан

табл.

4.

 

Т а б л и ц а 4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

* i

дг

 

%т

 

* i

х

2

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

1

4

2

 

 

2

 

0

0

 

 

 

0

 

2

4

3

 

 

3

 

1

0

 

 

 

0

 

3

4

4

 

 

4

 

2

0

 

• * .

0

 

4

4

1

 

 

1

 

3

0

 

 

 

0

 

Для автомата

АА

выбираем

s0 =

4

и z = хх. Для

случая

т = 2

полагаем

=

0, л:2 =

1 и по процедуре П4 строим

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

ность

 

 

 

р =

02 102 1102 11 1 0 2 П П 0 2

 

 

 

 

 

 

 

 

 

 

 

 

длины 19,

равной

оценке

(1.15). Легко

видеть,

что

оценка

(1.15)

достижима для заданного автомата для всех m > 2 и

любого началь­

ного состояния.

 

 

 

 

 

Т а б л и ц а

5

 

 

 

 

* i

 

 

 

 

 

 

 

 

 

Ч

 

хт

х \

*2

 

 

 

 

 

1

1

2

 

2

0

0

 

 

0

 

 

 

2

2

3

...

3

1

0

. • •

0

 

 

 

4

4

1

1

3

0

 

 

0

 

 

 

3

3

4

 

4

2

0

 

 

0

 

 

Пусть автомат АЪ задан табл.( 5 и для него г ~

хи

s0 =

1. Кон­

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

2, хг_=

~

0,

== 1,

равна

р = 02 102 102 102 102 .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ее

длина равна

14 и

совпадает

с оценкой

 

(1.16).

Легко

видеть,

что оценка (1.16) достижима для автомата АЪ для любого s 0

H m > 2 .

 

Процедура ҐІ4 впервые была предложена в работе [66] без

строгого

обоснования

(что было

отмечено в работе

[63 ]). Для длин

последовательностей, построенных по этой процедуре, в работе [66] найдена верхняя оценка (9), более высокая, чем (1.15).

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