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

ется

условие У5 и б (s, q) € Т f| Slt причем если J Т Г) S, | > 2,

то б

(s, q) фа(.

S Шюдиикратчайшееа.идовлетвориЛ

/теє У5

I

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

1.

Сначала строится

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

р' — zxx zx2

... 2 xhz,

где h — наименьшее

целое, для которого

6 (s0 , р') $-

Т0 (J Тг.

2.

К построенной ранее последовательности приписывается спра­

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

zh,

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

которого

б (s0 , р'г л - 1 ) $

Ге ;

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

состоящая

из

h

по­

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

3.

Затем, в случае необходимости, к ранее построенной последо­

вательности

дописываем

справа кратчайшую транслирующую

по-

O

i

Т а б л и ц а

1

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

ТФ0і

o

i

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

в л.1.

Рассмотрим

построение

кон­

1

2

6

0

0

трольной

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

для

2

3

б

0

1

автомата Л1, заданного табл. 1.

3

4

2

1

0

б

Пусть

s0

=

3,

4,

z = 001

и

4

5

1

0

0

(5, ООО) «=

{2,

3,

5,

6};

Для

5

6

4

0

1

любого V s

б (S, 00)

условие

(1.5)

6

2

5

1

1

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

Для

V = 6 ( S ,

00)

автомат

Av

не

имеет

правильной

нумерации слоев. На рис. 2 показан граф автомата Av

для такого

V.

Автомат Ау

имеет два слоя: {1} и {2, 3, 4, 5,

6}. На

рис.

2 прове­

дены дополнительные дуги (штрихованные), показывающие

переход

автомата А под действием последовательности г.

Для

V =

{2, 3, 5, 6} автомат А у — сильносвязен и, значит, име­

ет правильную нумерацию. Полагаем Те

и Т0

равными всему мно­

жеству состояний автомата А\ и 7\ = {1, 4}. Процедура Ш

строит

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

р — z (Oz)3 lzz3 0 Ozz2 0 (0z)2

lz 0 z2

0

г2.

Дужками выделены трансли­

рующие

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

Длина

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

р

равна 63.

В данном примере номер по­

следнего шага процедуры равен 17.

Возвратимся

к случаю

V =

= {2,3, 4, 5, 6}. Для

этого

слу­

чая

не

существует

правильной

нумерации

слоев автомата

Av,

однако

существует

процедура

построения

контрольных

после-

Рис. 2.

Автомат

Av\

для

V =

[2,

3,

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

аналогичная

4,5,6}.

процедуре

Ш .

Так

же,

как и в процедуре Ш , сначала строится последователь­

ность

р' =

zx1zx2z...zxllz,

а

затем к ней приписывается справа

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

и т. д. Построенная таким образом последова­

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

вид:

р =

z(0z)3 z3 0 (Oz)2 lzz3

00 Ozz,

d(p)

=

55.

1.

СтрбИТСЯ

ПОСЛеДОВатеЛЬНОСТЬ р'

= ZXxZh'X2Zh'-

... XfZ'f,

г д е

для всех

/, 1 <

I <

/,

1ц = 2, если б (s0 ,

zxxzh*

... X;) 6 Те,

и Л,

=

=

1 — в

противном случае; / — кратчайшее целое,

для

которого

8

(s0,

гх^

... xfzh!)

$

Т.

ранее,

приписываем

2.

К

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

справа последовательность q с указанными выше свойствами

и воз­

вращаемся в п.1 до тех пор, пока Т ф 0.

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

по про­

цедуре П2 для автомата Л1 (табл. 1) и V = {2, 3,

5, 6}. Напомним,

что s(

= 3 и г = 001.

Тогда полагаем, что Т0 =

Те — (1,

6} и

7\ =

{1, 4}. Процедура

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

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

рх

= z2 0z2 0z2

0z Oz2 0 Ozlz

00z2

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

ности p , построенной по П2 для

V =

(2, 3, 5, 6}. Для этой

последо­

вательности

Те

= {1}, Т. Но

поскольку

не

существует

последо­

вательности

q,

для

к о т о р о й

бу ( s 0 ,

pxq)

=

1, то

невозможно по­

строить следующий

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

с = (т + 1)п — и.

(1.8)

цедур и находятся

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

строенных

по таким процедурам.

Рассмотрим с т р у к т у р у последовательностей, построенных по ми­

нимальным

процедурам.

Теорема

1.5. Процедура является минимальной

тогда

и. толь­

ко тогда, когда на любом j-м шаге этой процедуры,

1 <1 /,

одновре­

менно выполняются следующие

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

гі = е

(qj = е А

б (So, р/_2?/-іО-і) € Т'Ґ),

0 -9)

гі = А- -> б (So, />/_,?,) є 7 І - 1 .

(1'. 10)

зе

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

Пусть

П — минимальная

процедура

из К-

Если г, =

е и

ф е, то pj =

pj^iq/z,

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

всех

г £ R Т'г~х

=

Ті.

Это

значит,

что на /-м

шаге для

всех г

из Т°г

не удаляется

ни

одного состояния, т. е. процедура не мини­

мальна. Если Гу =

е,

qt

=

е

и б (s0 ,

р/ _2 <7/_і/'/_і)

(£

Г І - 1 ,

то pr- =

= pj-2qi-\rj-\zz,

но

7 Т - 1

=

Т'е. Значит, для всех г Т'г

=

Г / - 1

и про­

цедура не минимальна. Таким образом,

если

П—минимальна,

то

выполняется

(1.9).

Пусть

П — минимальна,

rf

=

х

и

б (s0 ,

Ps-\qi) і Т'Г1

для

некоторого /.

Тогда

Т'Г1

= Т'х, а

значит,

для

всех г Т'Г'

=

ТІ-

Таким

образом, если П — минимальна то

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

(1.9),

(1.10). Рассмотрим произвольный

/-й шаг, / >

1. Если fj =

е,

то

р/ =

p'zz

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

вательности

р'

и б (s0 , р')

£

Т'е~1 .

По

условию У6

(раздел 1.2)

б (s0> Р') €

Т'е,

т. е. состояние б (s0 ,

р')

удаляется из

множества

7^. Если

Tj — х, то

из соотношения (1.10) и условий

У5—У6

(раздел 1.2) следует, что на /-м шаге состояние б (s0 , P/_i<7/)

удаля­

ется из Т°х. Поскольку

\ Т°\ = (m +

1) п — и, то выполняется

(1.8) и

процедура

П — минимальна.

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

окон­

чено.

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

Пусть J = {Д,

j g } , где q — mn —г и, и если

1<Сі, то ii<Zji-

Через lq] обозначим

целую часть положительного

действительного

числа q. Используя введенные обозначения, дока­

жем следующую

теорему.