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

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

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

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

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

Добавлен: 30.06.2024

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

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

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

Таким образом, комбинационная схема К реализует отображение

К:(1Л, . . . . У„)->#.

Такие наборы R назовем векторами различимости для задачи рас­ познавания автоматов известного класса. Если при подаче на вход

автомата А входного

сигнала х с выхода

комбинационной схемы

К

получен некоторый

вектор различимости R, то это означает, что

те автоматы Л,- и A-t в

классе, для которых

at Ф as

в

векторе

R,

различаются этим входным сигналом. Если в векторе R

компоненты

о,- и а і равны, то это

будем обозначать следующим

образом: а,-

=

=

ajlR].

 

 

 

 

 

Легко зіметить, что типы н количество векторов различимости зависят только от числа п автоматов в классе и мощности выходного алфавита J Y | = k автоматов и не зависят от других характеристик класса.

В дальнейшем будем рассматривать только множество векторов различимости R, которые могут быть получены с выхода комбина­ ционной схемы К.

При k >- п каждый вектор различимости R можно взаимно од­ нозначно сопоставить с некоторым разбиением множества из п

элементов,

которые будем обозначать

через я « . Это разбиение оп­

ределяется

следующим

образом:

 

 

 

і = /(яя)«-»а, =

а/[/?].

(3.3)

Тогда

max о,- +

1 показывает число классов

этого разбиения,

cij = I означает, что і-й элемент находится в 1-ом классе разбиения. Поэтому векторы различимости R можно рассматривать вне данного конкретного класса автоматов, а относительно любого клас­

са автоматов, состоящего из данного числа автоматов.

Введем на множестве векторов различимости R при /г >- п сле­ дующее отношение:

 

Яі <

Я* < - V M ,

К =

аіг [R2]

 

аіг

[/?J).

(3.4)

Отношение (3.4) обратно отношению порядка

на

множестве раз­

биений множества из п элементов, которое определяется

 

следующим

образом:

лг - < л;2 <-> (Ї == / (лх ) -*-і =

\ (я2 )).

 

 

(3.5)

 

 

 

 

Согласно работе [9], отношение, обратное частичной

 

упорядочен­

ности, является

само частичной

упорядоченностью. Следовательно

отношение (3.4) на множестве векторов различимости R

при k > - /i,

является отношением

порядка.

 

 

 

 

 

 

В силу взаимно однозначного соответствия между множеством

векторов различимости

R

при k >• п и множеством разбиений мно­

жества

из п элементов

и наличия частичной упорядоченности (3.4)

и (3.5)

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

являются

двойственными

друг

другу.

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

лив следующий

принцип

двойственности

[37J: если

справедлива

какая-то теорема о частично упорядоченных множествах, сформу­ лированная в общелогнческих терминах и терминах порядка, то справедлива и двойственная ей теорема.

Принцип двойственности позволяет заменить изучение свойств частично упорядоченного множества векторов различимости R изу­ чением свойств частично упорядоченного множества разбиений мно­ жества из п элементов.

Введем некоторые, необходимые в дальнейшем, понятия теории частично упорядоченных множеств [9, 37].

Пусть задано частично упорядоченное множество 5 и его непу­

стое подмножество

Т.

 

Элемент s £ S называется точной верхней гранью множества Т,

если s >> і для

всех

t £

Г и из справедливости соотношения s > - 1

для всех t £ Т

вытекает,

что s ;> s (s Є S). Двойственным образом

определяется точная нижняя грань множества Т.

Точную верхнюю грань множества Т в частично упорядоченном

множестве 5

будем обозначать

sup Т, а точную нижнюю грань —

i n f Т.

 

 

Частично

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

множество называется структурой,

если всякое его двухэлементное подмножество имеет как точную верхнюю, так и точную нижнюю грань.

Непосредственно из определения видно, что частично упорядо­ ченное множество, двойственное структуре, само является струк­ турой. Отсюда вытекает возможность применения к структурам принципа двойственности.

На множестве разбиений множества из п элементов введем две

операции.

 

Разбиение я х • я 2

называется произведением разбиений щ и я 2 .

Оно определяется соотношением

Vs,< (S =

t (Щ • Я 2 ) «-> S = t ( я х ) A s = t ( я г ) ) -

Разбиение я х + я 2 называется суммой двух разбиений я х и я 2 , элементы sat находятся в одном классе разбиения пг -+- я 2 , если существует последовательность элементов S = s0 ) slt s2 , s„ = t, удовлетворяющая условию

V o « r s n - i ( s ; = s H - i ( % ) V SL = s 4 - i ("a))-

Известно (например, [60]), что множество

всех

разбиений мно­

жества из п элементов с отношением (3.5)

 

является

структурой,

причем

 

 

 

sup (яъ я 2

 

 

 

-f- я 2 .

 

i n f ( я х ,

я 2 ) =

я 2 •

я 2 ,

)

=

я х

 

- Разбиение, в котором

все

элементы

входят в

один класс, назы­

вается единичным. Это наибольшее из

всех

 

разбиений,

будем обо­

значать его через I .

 

 

 

 

 

 

 

 

 

Разбиение, в котором в каждом классе

содержится

только по

одному элементу,

называется

нулевым. Это

наименьшее из всех

разбиений, будем

обозначать

его

через

О.

 

 

 

 

 

Структура L называется структурой с дополнениями, если имеет место

V s 3 < ( i n f ( s , 0 = О Д sup(s, 0 = 1).

Интервалом [а, Ь] называется подмножество Т частично упоря­ доченного множества 5, удовлетворяющее условию

V/ £ 7 - (fl<i<fc) .

Структура L называется структурой с относительными дополне­ ниями, если

 

V[a .6]siV/e[a .b] 3 s ( i n f (t, s) =

а Д

sup(;, s) =

b).

Атомом

частично упорядоченного

множества 5 с

наименьшим

элементом 0 называется такой элемент s £

S, что s >

0, и из того,

что t >• 0

и / < . s, следует t = s.

 

 

 

Атомом во множестве разбиений множества из п элементов яв­ ляется такое разбиение, все классы которого, кроме одного, где два элемента, состоят из одного элемента. Таких атомов будет С"п.

Справедливы следующие утверждения [9]:

1)любое разбиение множества из п элементов является суммой некоторых атомов;

2)структура L является структурой с относительными допол­ нениями, если каждый ее элемент является точной верхней гранью некоторого множества атомов.

На основании этого приходим к выводу, что структура разбие­ ний множества из п элементов является структурой с относитель­ ными дополнениями.

Говорят, что элемент s частично упорядоченного множества S покрывает элемент t этого множества, если s > ( и

 

Vpes {p>t

Л Р < s

Р = s ) -

 

 

Структура L из конечного числа элементов называется полуде-

декиндовой, если

ее элементы удовлетворяют

условию: для всех

s, /, р £ L из того, что s, t покрывают р и s=£

t,

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

ная верхняя грань (s, /) покрывает s и t.

 

 

Разбиение я

покрывает

разбиение

я 2 , е с л и

в с е

классы разбие­

ния я х , кроме одного, совпадают с соответствующими классами раз­ биения л2 , а один класс разбиения пг является объединением двух соответствующих классов разбиения я2 .

Лемма 3 . 1 . Структура разбиений множества из п элементов

является

полудедекиндовой.

 

 

 

 

 

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

Требуется показать,

что если произ­

вольные разбиения я х , я 2

и я таковы, что я х

и я 2

покрывают я, то

я 2 + я 2

покрывает я х и

я2 .

 

 

 

 

Пусть разбиение я содержит классы b±,

Ь2,

 

bk. Тогда разбие­

ние я^ содержит классы bx, Ь2,

bk—\ U bk,

(всего (k — 1) классов),

а для разбиения я 2 возможны две ситуации:

 

 

1) оно содержит классы Ьг,

Ь2,

. . . , & * _ ] , bt

[}

bk ((k — 1) классов);

2) оно содержит классы bx,

b2,

bt (J bj, ....

bk ((k — 1) классов).

 

Тогда

в первом случае разбиение пл + я,

содержит

классы Ь1У

Ь2,

£>,- U bk~\ U bk (всего

(/г — 2)

класса"), причем

все

классы,,

кроме одного, те же, что и в разбиениях лх и я2 . Класс ft (J

 

(J

для it! является объединением классов bj и б*-! U bk,

а для п 2 — объ­

единением классов £>,• U Ьк и І>А- і • Таким образом, я а +

я 2

покрывает

яг

и л2 .

 

 

я 2 содержит такие классы: Ьг,

 

 

 

Во втором случае яг +

Ь2>...

все

bi\}bj,

£>*_i (J bk

(всего

(А — 2) класса). В разбиении щ

+ я2 .

классы, кроме одного Ьс[) £>;-,те же самые, что

и в

 

a

 

является

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

двух

классов

из nv

Аналогично,

% - j - л2 .

содержит те же классы,

кроме одного

bk—i U bk, что и разбиение я2 ,

a

(b/i-i (J 6ft есть объединение

двух классов из

яа .

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

и в

этом

случае лх + я 2 покрывает я х

и я2 .

 

 

 

 

 

 

 

Таким образом, доказана такая теорема.

 

 

 

 

 

 

 

Теорема 3.1. Множество разбиений

множества

из п элементов

с

отношением порядка

(3.5)

является полудедекиндовой

структу­

рой

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

дополнениями.

 

 

 

 

 

 

 

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

называется еще М-структурой [9].

 

 

 

 

 

 

 

 

Используя принцип

двойственности, приходим

к

следующему

результату: множество векторов различимости при k >• п для задачи распознавания автоматов известного класса с отношением порядка (3.4) является М-структурой.

Определим число векторов различимости в М-структуре. Рассмотрим множество всех неупорядоченных разбиений числа

я на / частей, которое определим следующим образом:

 

 

 

Л

(ri>r2>

•••

>г!>1)\.

 

(3.6)

Определим

отображение

ф множества

векторов различимости

в множество

Q:

ф(ві. а2

ап) = (rv

г2 ,

. . . , г,),

 

(3.7)

 

 

 

 

где / =

max ас

-\- ] ,

rt — число одинаковых

компонент

в

векторе

 

і

 

 

 

 

 

 

 

 

 

 

различимости

R

= (ах , а2 ,

...,а„). Например,

ф (0,1, 1,

1,

2, 0,

Зр

1, 4) =

(3, 2,

1, 1, 1). Найдем число прообразов набора

(г, г2 ) . ...

г,) по отображению ф. Введем отношение эквивалентности є

на

множестве {1, 2,

/}, определив его соотношением

 

 

 

 

 

 

 

(І,

Г{ =

г/.

 

 

 

 

 

Лемма 3.2. Число векторов различимости,

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

на­

бору (rlf

г2, ....

л,), равно:

 

 

 

 

 

 

 

 

 

 

 

 

П^П, . . .

п,

 

 

 

(3.8)

 

 

 

 

 

 

 

 

 

 

где П/ — количество перестановок из числа

элементов j-го класса

эквивалентности є; | е | — число классов эквивалентности.

Д о к а з а т е л ь с т в о . Действительно,

п компонент векторов

различимости должны распределиться по / блокам. Эта задача яв­ ляется классической. В качестве ее решения приведем теорему Феллера [45].

Пусть ги г2,

Г[ — целые неотрицательные числа, причем гг 4-

•+- ?2 + • • - +

т{ = п и все г( >- 0. Тогда число способов, посредством

которых п элементов могут быть распределены на / групп, из ко­

торых первая содержит гх

элементов, вторая — г2 элементов, и так

далее, 1-я — г1 элементов,

равно

 

п I

 

г, ! г3 ! . . . г,! '

Здесь порядок групп существенен в том смысле, что, например, раз­ биения числа л = 5 на две группы (гх = 2, г2 = 3) и (rt = 3, г2 = 2) считаются различными, однако порядок элементов внутри группы не учитывается. Заметим, что в отличие от классической задачи, здесь порядок равных по мощности групп не существенен. Это сле­ дует из построения векторов различимости., В связи с этим полу­ чаем окончательную формулу (3.8).

Зная п, можно определить число элементов множества Q неупо­ рядоченных разбиений числа п на части [47] Согласно лемме 3.2, находится число векторов различимости, соответствующих одному

набору {гх, г2,

rs). Просуммировав по всем элементам множества

Q, получим число векторов различимости

в /W-структуре. Пусть

q — (г\ч\ г2ч),

г\ч)) —элемент

множества

Q. Тогда справедлива

такая теорема.

 

 

 

 

Теорема 3.2.

Число элементов

М-структуры

векторов различи­

мости для класса из п автоматов при k > п запишется в виде

 

Ч - І і ^ -

п , п . . ' . п , „ -

М

1=]

Пр и м е р . Пусть дан класс из четырех автоматов и k >- 4. Определим число элементов /И-структуры. Множество Q будет со­ стоять из наборов: (4), (3,1), (2,2), (2, 1, 1), (1, 1, 1, 1).

Тогда согласно теореме 3.4

д, __ 4!

41

4!

1

4!

1

,

41 " t " 3 ! I ! +

2 l 2 I ' 2!

21 1 І 1 I " 2!

+

j

1 !

. - L

- = 1 4 - 4 4 - 3 - 4 - 6 4 - 1 = 15,

r

1! 11 I ! I I

4!

т

т

где N — число векторов различимости.

Рассмотрим детальное строение М-структуры векторов разли­ чимости.

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