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

ности. Заметим, что по заданным Q, А'

= (S, X,

б) и s0,

t0 £ S авто­

мат Ал,

а значит, и ср строится единственным образом,

без перебора.

Задача

нахождения эквивалентности

я с ф с

наименьшим числом

Вернемся к задаче синтеза. Пусть заданы А'

=

(S, X, б) и регу­

лярное событие Q s

X* — [е].

Решая частную

задачу

синтеза

для всех s, і £ S, s Ф

t, получим множество отношений cps(.

По этому

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

Ф = П <Ps<-

Нетрудно

показать,

Пусть

N = {1,

п\ и пусть задано некоторое отношение

Ф с N X

N.

условия:

а) я Е ф;

ф, если я 1 Ф л, то л 1

ct. л.

б) для любой эквивалентности я1 s

Эквивалентность л на множестве N назовем оптимальной,

если

для нее выполняются условия а);

в) для любой эквивалентности л 1 s

ф число классов эквивалент­

9

2—1686

129

шения ф, |ф' | = 21, В = р^ф', \ В\ — k. Каждой

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

л

поставим во взаимно однозначное соответствие

разбиение П =

=

{Л (О)} a£N-

для которого выполняется соотношение С X С g

<р' (J iN,

где Ц/ —

тождественное преобразование множества N. Очевидно, что

где «

=

| С|.

k > г >

и,

Теорема 8.2. Для любого отношения ф и любой эквивалентности

п £ Кы

(ф) число г классов эквивалентности не превосходит величины

d, где d — наибольшее

целое, для которого d (d — 1) < ; 2t.

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

Произвольно

зафиксируем

ф.

При

ф' =

0

теорема

очевидна.

Пусть

ф' Ф 0 .

Очевидно,

что

k х

x(k

— 1) >

2t. Следовательно, k >

d. При

k = d 21 =

k (k — 1)

и для всех a, b £ В, а Ф b, (а, Ь) £ ф'. Следовательно, ни одна

пара

a, b £ В, а Ф

Ь,

не может находиться в одном классе эквивалент­

ности л £ Кк

(ф).

С

другой

стороны, в силу

максимальности л,

личных классов Ki,

Kj

£ П, существует пара (а, Ь) £ ф', для

кото­

рой а £ Kt, b £

Kj-

Число

неупорядоченных nap различных

клас­

сов из П равно

Г^Г

2

^ и

н е превосходит величины t. При г > d

Алгоритм

А\.

1.

Кх : =

{1}; К2

••=••• :=Ка:=

0 ;

s: = 2 .

2.

Если s > п, то

конец вычислений,

иначе переходим к п. 3.

5.

Kj

'• =

Kj U [s).

6.

s: =

s +

1

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

7.

/ :

=

/

+

1.

8.

Если

Kj =

0 , то переходим к п. 9, иначе переходим к п.

4.

9.

К/: =

{s}

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

В

результате

работы алгоритма Л1 получаем разбиение П

=

= (К\,

Кг),

где г — наибольший номер непустого класса.

Запись П =

{/Єї,

Кг) в дальнейшем будет означать, что

клас­

сы разбиения неупорядочены, а запись П = (ky,

kr) — что

клас­

гично, через Kt

=

\К\, •••,/C's.J

будем

обозначать

класс, в

котором

элементы

неупорядочены и

через

К І =

[k\,

k's) — класс, в ко­

тором элементы пронумерованы в порядке их

занесения в класс /С,-.

Пусть М

=

(а1г

ап) — некоторая перестановка множества N.

Разбиение П, полученное алгоритмом А\ из перестановки

М,

обо­

значим через

П (М,

ф). Эквивалентность,

соответствующую

раз­

биению П (М,

ф), обозначим через я (М, ц>).

Теорема

6.3. Эквивалентность я

(М,

(р) максимальна

для

всех

отношений

ф и перестановок

М.

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

Пусть

ф

и

М произвольны.

Пусть

П == П (М,

ф) =

(Ki,

КГ). Из

п. 4 алгоритма А\ следует,

что

я

s

ф.

Пусть

Пл =

{/?д,

RV]

—разбиение,

не

равное

П и

Я! Е Ф- Пусть і <с /

и К( U К/ є

R;- Рассмотрим работу

алгорит­

ма Л1, когда s =

k{-

Поскольку

s ^

Kt,

то (s, b)

£ ф'

для

некото­

рого b £ КІ-

С

другой стороны,

s,

b £ R„

значит,' (5,

b) £ ф. Сле­

довательно, я максимальна и теорема доказана.

Класс всех эквивалентностей

я (М, ф) для некоторого

отноше­

ния ф обозначим

через К А (ф)- По теореме 6.3 КА

(ф) s

Км (ф) для

всех ф.

Пусть для произвольного отношения ф и произвольной

переста­

новки М

П (М, ф) =

(Ki,

Кг)-

Имеет место следующая лемма.

Лемма 6.3.

1. Если для всех

b £ К І

(а,

Ь) £ ф, то а £

с

U К/.

2.

6) €

Ф, то а £ К\, т. е.

/=і

Если для всех

b £ N (а,

N^— В s

Ку

3. Если k Ф

0, то | К\ | >

п — k +

1.

4. Если множество N — В не включается ни в какой класс макси­

мальной эквивалентности я, то я

^

/Сл (ф)-

5.

ф' ф

0

г >

2.

S+1

6.

|ф [а) \ =

а £

U /С/.

Пункты

/=і

вытекают из описания

1, 2, 5, 6 леммы непосредственно

алгоритма Л1. Пункты 3 и 4 следуют из пункта 2 леммы.

Рассмотрим следующий вопрос: для всякого ли отношения Ф

существует такая перестановка М,

из которой с помощью алгоритма

Л1

строится

оптимальная эквивалентность.

Положительный

ответ

на этот вопрос дает следующая теорема.

Теорема 6.4. Для всех отношений ц> существует такая переста­

новка М,

что л (М, ф) — оптимальна.

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

Пусть

зафиксировано

некоторое

от­

ношение

ф

и

я 2

— оптимальная

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

для

которой

9»

131