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

что

(tu

ft)

£ Z (p). Но в этом случае

(sl t rx ) £

Z (p)

по

УЗ,

где

(s;,

О)

=

Ьі> ЯіП) — (*/.?/)• П У С Т Ь Для

всех

/ <

і —

1

g7) £

gZ (p). По сказанному выше, для всех

/ < і

—

1 (s/, г,)

£ Z (р).

Покажем,

что

(tit

qt) £ Z tp).

Пусть

qt

— х\Хч...

,х;.

По

условию

У5

для

всех

h,

1 < h < f,

б (s„,

... *д_і)

£

Т°< — Т'г 1 .

Это

значит,

что

для

всех

h существует

і — 1,

xh

xh

k <;

для

которого

б

(s0 ,

х[ ...

Хн-l) £

Vk-,

т. е.

(б

(s„,

jci

... ХЛ _і). Xh) =

(Sft, Jtft) И no

предположению индукции (б (s0, x\ ... Xh-i),

Xn) Є Z (p).

Тогда

no

условию У2 (tit

q£)

£ Z (p).

Таким образом, для всех

/

выполня­

ется

соотношение

(tj,

qj) £ Z (р),

а

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

и

(s/, Г/)

£

£ Z (р). Из последнего соотношения вытекает, что (

(J

Г°

X {л:})

S

s

2 (р). Учитывая, что

Г° х

{z} s

Z (р),

получаем

соотношение

Z°

s

Z (р), которое доказывает теорему.

Следствие 1.1. Пусть дана произвольная

процедура из класса /<",

для которой

для всех г £ R.

Любая

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

построенная с помощью этой процедуры,

является

контрольной

для автомата

А.

Следствие

1.1

непосредственно

вытекает из

теорем

1.1

и

1.2.

В общем случае, для того чтобы с помощью процедур из К стро­

ились

контрольные последовательности, не обязательно

для всех

г £ R полагать множество Т°г

равным множеству

всех

состояний

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

z = z'w для

некоторых г'

£ X* и w £ X.

Пусть

б (S,

z') =

(J

б (s, z'). Для произвольной

процедуры

П из класса

К

для

всех

г £ R — {w} полагаем Т°г

= 5

и Tw =

S — V,

V—

за­

данное множество, для которого

V ^ б (5, z'). Такое задание мно­

жеств Т°г назовем стандартным.

Процедурой, покрывающей множество V, назовем такую П £

К,

для которой множества Т°г заданы стандартным способом, а V —

множество, для которого множество Z0

операциями сложения и вы­

читания переходов порождает множество S х X*.

Процедуру

П,

покрывающую множество V, будем обозначать через П (V).

Пусть

дана

произвольная

процедура

П (У).

По

теореме

1.2

Z° g Z ( p )

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

(V).

денных

из Z0

операциями

сложения и вычитания переходов авто­

мата А,

содержится в множестве Z (р). Тогда из определения

П (V)

следует, что Z (р) =

5 X X* и из теоремы 1.2 вытекает следствие.

Следствие

1.2.

Любая

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

с

по­

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

П (V),

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

по­

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

для автомата

А.

Рассмотрим

следующее

условие:

(V

х И )

П U =

0 ,

(1.5)

ГДЄ U =

{(S, X){3t&S^i,l^k(.(8(t,

Хг . . .

*,) = (s, X))}

и z =

= XtJC2

. . . xkw.

Теорема 1.3. Любая процедура

из I(

со стандартным

заданием

множеств Т°г, для которой выполняется (1.5), покрывает множество V-

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

Пусть для процедуры П £ К. выпол­

няется

(1.5). Поскольку Т°г

=

S

для всех

г Є R — {w}

и

Т% =

= S —

V, где V є б (S, г')

и

г = /во,

то

Z°\J(V X {w})

= 5 х

X XU«Sx {z}. Множество S

X X

при

помощи операций

сложе­

ния и вычитания переходов порождает множество S X X*.

Поэтому

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

V х

{w}

порождается

множеством Z0 .

Очевидно,

что U Е Z0 . Поскольку

переход (s, z'),

где z' — начальный отрезок

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

для

которого

z = z'w, для всех

s

Є S

есть

сумма некоторых переходов из U, то

переход (s, z')

порождается

множеством Z°. Поскольку переход

(б

(s, z'), ш) есть разность пере­

ходов, (s, z)

и (s, г'),

то

любой

переход (б (s, z'), tw)

порождается

множеством

Z°.

В

силу

V s

б (5, г'), любой элемент из V х

{да}

порождается множеством Z0 , что оканчивает доказательство теоре­

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

П. Оценим

величину с.

Из условия У6 следует, что на каждом

/-м

шаге, 1 <

/ < с, про­

цедуры найдется не более одного г £ R и

не более одного состояния,

всех г,

то с >- 2

\Т°г\

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

с >

( т +

1)

п — и, где

п — \S\, m ~\Х\,

ц =

j V|.

Полученное

неравенство

позволяет

оценить

снизу

длину

d (р) последовательности р.

Из

условия

У5

следует,

что

d (Pi) =

d (p; _i)

+ d (ft) + d (rt) +

d(z),

где р/

—

процедуры П.

Пусть

d (z) =

L . Учитывая,

что d (ft) > 0

и что

d (гу) Ф О не

менее,

чем

на тп — и шагах

процедуры, получаем

d(p) > ( ( m +

I ) n — и + 1)L +

пгп — и.

(1.6)

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

ft,

входящие в

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

ложено условие: если ft Ф е, то

ft — кратчайшая последователь­

ность, для которой б (s0 , P/_ift)

Є \}T'r~l. В дальнейшем рассмат-

ф 0, где 0

— пустое множество.

г

Пусть множества

Т? для всех г

£ R

заданы следующим обра­

зом: для всех

г £ R

—- {w} и Т° =

5 T°w

= 5 — V, где V — неко­

которое принадлежит множеству

(J Т'г, и, следовательно,

не.сущес-

т

твует такого целого с, для которого

U Т°г = 0. Определим

достаточ-

г

автомат Ау =

(5, X,

бу), где

или sPV,

Е

,

s

[б(s, х), если хФw

by (s,

х) =

\ к

^

v-

Слоем

автомата

{не определено в противном случае.

называется

наибольшее сильносвязное подмно­

руем все слои автомата Ау

номерами от

1 до

k.

Определение

1.3.

Нумерацию слоев автомата Ау назовем пра­

вильной, если для нее одновременно выполняются условия:

1.

Для

слоя Slt 1 <

і <Z k,

существует ровно один выделенный

переход (a,-, xt),

для

которого

бу (at,

xt)

определено и

бу (яг, хс)

£

£

Si+i.

Если 6у (s, х)

определено для

(s, х), не равного

(at, х{),

то

8у

(s,

х) £

Sc.

2.

Для всех s £ Sk

и х £ X,

если

бу (s, х)

определено,

то

бу

(5,

3.

s0 є

sx.

б (s, z)

£ S,„ где h <

4.

Для всех s £ Sh

1 <

і <

k,

i.

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

назовем

S 0 - O 6 X O A O M

автомата

Ay,

если

для любого перехода

(s, х) найдется последовательность plt

для ко­

торой

рхх

< р

и 8у (s0 ,

рх)

=

s. Из

условий

Уб — У7

вытекает,

что всякая

последовательность, построенная по П (V), является

s0-

ми I — 3 . Покажем, что существование нумерации со

свойствами

1—4 достаточно для существования процедуры П (V)

£ К- Дока­

мата Ау, то существует процедура

из класса К, покрывающая мно­

жество V.

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

Пусть

S l f

Sk

— п р а в и л ь н а я

н у ­

м е р а ц и я с л о е в а в т о м а т а Ау. Полагаем, ч т о Tr=S

д л я г Ф wn

ТІ, =

= S — V. Далее полагаем р0

= г. Тем с а м ы м

в ы п о л н и м н у л е в о й

б (s0 ,

z) Є Sy

Пусть

в ы п о л н е н о

/ —

1 ш а г о в п р о ц е д у р ы ,

п р и ч е м

Tj^\

=

U Т'~1

Ф 0.

Предполагаем,

ч т о н а в ы п о л н е н н ы х

ш а г а х

процедуры в ы п о л н я л о с ь п р а в и л о :

если н а / - м ш а г е ,

1 < / -< /" — 1,

из м н о ж е с т в а

Т°г д л я н е к о т о р о г о

г £ R

у д а л я е т с я

с о с т о я н и е , при­

н а д л е ж а щ е е с л о ю S[y

т о в с е с о с т о я н и я с л о я Sz_i у ж е у д а л е н ы из

Т°г д л я

в с е х

г, а с о с т о я н и я с л о я S t + i

и з м н о ж е с т в ТІ для

в с е х г

в е р к и слоев и

п . 3 о п р е д е л е н и я

1.3 следует, что

h •< і •< h +

1.

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

q/,

д л я к о т о р о й

в ы п о л н я ­

ются условия by (tj, g/) £ U Т{~1,Ьу

(tj,

g,)

Є St и д л я в с е х

q'x

• < q\

т

с о с т о я н и е

8у

(tj, q')

у д а л е н о и з

м н о ж е с т в а

Т°х.

Поскольку каждый а в т о м а т н ы й

с л о й — с и л ь н о с в я з н о е

м н о ж е с т в о

с о с т о я н и й , т о согласно п . 1 о п р е д е л е н и я

1.3, д л я всех s £ Sh

и t £ Sh

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

q т а к а я , ч т о 8у (s,

q) =

t. Значит,

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

q/ в с е г д а

существует. При этом

может б ы т ь д в а случая. Пусть выполняется

соотношение

5,

П Tj-i

= {а,.} Л St

П (Г? _, -

Г*"") =

0 ,

(1.7)

г де

(at, Xi) —

с п е ц и а л ь н ы й

п е р е х о д ,

о п р е д е л е н н ы й

в

п . 1 о п р е д е л е ­

н и я

1.3. Тогда 6 7 (tj,

qj) = at.

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

=

= pi^iqjXtzz,T.

е . полагаем q/+i =

г; +і =

е и rj — xt.

По

у с л о в и ю

У6 Т'х. =

T'x~l

—

{at}

vT'r

= ТГ1

для в с е х

г, г ф

xt.

По

э т о м у

же

у с л о в и ю

ТІ+1

=

ТІ — {by (au

xt)\ и

д л я всех х

Тх+1

= ТІ

Пусть

соотношение

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

Тогда

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

п о с л е ­

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

qj в ы б и р а е м

т а к , ч т о б ы

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

г 8у

(tj,

qj)

£

Є Т'ГУ и

(ду (tu

qt),

г) Ф

(ОІ,

Х[).

Такая п о с л е д о в а т е л ь н о с т ь

в с е г ­

д а с у щ е с т в у е т .

ЕСЛИ

Г =

Є, ТО СТрОИМ

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

P/-I-1

=

=

pj-\qjZZ,

т.

е. п о л а г а е м

/7 =

r / + i =

q l

+ i =

е.

По

условию

У6 ТІ =

Г Г 1

д л я всех г,

ТІ+1

=

Г'с — {ду (tj,

q,))

и Tx+l

=

П

д л я .

всех

х £ X. Если г Ф е,то строим последовательность

pj+i

—

=

pj_\q,rzz

п р и бу (£/, 9/г) £

Т'е~1 кр/ = pj—\rz — в п р о т и в н о м

слу­

ч а е . По У6 с т р о и м

м н о ж е с т в а Т / + 1 и л и ТІ.

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

предполагая, ч т о /

—

1 ш а г о в

п р о ц е д у р ы

выпол­

н е н о , выполняем с л е д у ю щ и й / - й ш а г (j-й и /

+

1-й шаги) п р о ц е д у р ы ,

причем н а й д е т с я такое г £ R

и состояние

s,

которое

удаляется из

Следствие

1.4.

Пусть

у

автомата

Л т > 2 ,

где т =

| Х|, и для

всех х £ X xz' Ф

г, где z =

z'w. Если существует правильная нуме­

рация

слоев

автомата

Ау,

то существует процедура П (V) с как

угодно большим числом шагов.

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

Пусть у автомата А т >• 2 и для

всех

х xz' Ф

z. Поскольку т >• 2, то найдется такое х', что х'

Ф гих'

Ф

Ф w,

где w £ X.

Тогда полагаем

= 5.

Пусть

существует

ения процедуры из доказательства теоремы 1.4, выполняем /

шагов

процедуры, для которых Т!х. Ф 0.

Затем

выполняем k шагов про­

цедуры от

/ +

1-го

до / +

6-го, полагая,

что для

всех i, j +

1 •<

•< і •< / +

k,

г, =

е.

Тогда в силу того,

что для всех х xz'

Ф г,

получаем

равенство

ТІ? =

T'J~k Ф

0.

Затем опять применяем ме­

тод построения из

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

теоремы

1.4 и выполняем

П (V)

до тех пор, пока на с-м шаге, с >

/ +

k,Tc

= 0.

Поскольку k мо­

жно выбрать

как угодно большим, то с будет как угодно большим.

{О, 1}. Кроме того, полагаем, что множество

V задано так, что вы­

полняется соотношение (1.5). Полагаем, что 7 ^ , = 5 — V и

7 ^ = 5

для г Ф w. Пусть S i ,

Sk — правильная нумерация слоев автома­

та Ау

и (a,, xt)

— специальные

переходы, описанные в п. 1 опреде­

ления

1.3.

Процедура

ПЛ. Блок-схема

процедуры представлена на рис. 1.

При описании

процедуры опущен индекс jnTin

в q/, что не приво­

дит к двусмысленности. Кроме того, полагаем, что Т = U Тг.

Работа