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

Во-первых, М-структура содержит

наименьший элемент R0

=

= (0, 0,

0), который обозначим через 0^, и наибольший элемент

Rma-x =

(0,

1,2,

П — 1), КОТОРЫЙ обоЗНЭЧИМ Через IR.

Во-вторых, в уИ-структуре можно выделить подмножества

элементов, которые назовем уровнями.

Уровнем /W-структуры, имеющим номер т, назовем подмноже­

ство векторов различимости R, в каждом из которых самый большой

компонентой

является а, ~ т. В этом

случае М-структура имеет

п уровней с

номерами: 0 , 1 , 2,

т,

п —

1. Уровень с номером

0 состоит из

одного элемента R0

=

OR, уровень с номером (п — 1)

также состоит из одного элемента Rmax=

JR.

Определим

число элементов — векторов

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

уровне

с номером

1. Это —векторы

вида R

= (0, а2,

а'п),

где

все а{ £

[О, I } , и обязательно в каждом векторе есть а,

= 1.

Очевидно,

что

число таких векторов совпадает с

количеством

(п — 1)-значных двоичных чисел без одного, т. е. равно

(2Л—1 — 1).

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

уровнях с номером 0, 1, 2.

В этом случае

векторы различимости представляют наборы R =

= (0, аг,

ап),

где все а, £ (0, 1, 2| есть числа троичной системы

превосходит З п — Н а б о р ы ,

не являющиеся

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

мости, имеют вид (0, 0,

0, 2, ак,

ап). Всевозможных наборов,

у которых первые две компоненты

равны 0,2,

имеется Зп ~2 . Набо­

есть R т (0, 0

0, 2). Таким образом, число всех наборов, ко­

торые не являются векторами различимости равно Зл—2 + 3 " _ 3

... + 3 + 1 =

(3"—1

—

1)/2. Тогда число

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

на уровнях с

номерами 0, 1, 2 равно:

З"-1

_

(З"-1 — 1 )/2 = ( З " - 1

+ 1 )/2.

/?!

U Я я =

Я *+ я* =

я*, • я*„

(3.10)

Ri

П Я2 =

Я ~ я я =

я Л г + яя,.

(3.11)

5

2—1G86

65

различимости для класса

автоматов. В основу алгоритма

положим

связный

неориентированный граф без

циклов — дерево,

которое

обозначим

через Т. Дерево Т

д

имеет

корень — вершину

с

отметкой

0.

Корень

дерева

связан ребрами с двумя вер­

шинами,

имеющими

отметки

0 и 1. Произвольная вершина

дерева

с

отметкой

t

связана

ребрами с

вершинами, имею­

щими отметки 0, 1,2

d, где

d = l +

l.

Процесс построения дерева

осуществляется до

{п — 1)-го

0

і 2 О і

2 0 1 2

0

1 2 3

уровня. Из процесса

построе­

Рис. 8. Дерево Т для нахождения векторов

ния следует,

что цепи длины

различимости при л = 4.

(п —

1) от

корня

дерева

до

всех

конечных

вершин цепей дают все

векторы

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

данного п,

получающиеся

как

наборы

отметок

вершин,

принадле-

Л, =

(0,

0,

1,

1),

/?4

=

(0,

0,

1, 2), Rb =

(0, 1,

0,

0),

t

Я, =

(0,

1,

0,

1),

Я7

=

(0,

1, 0,

2),

/?8

=

(0, ,1,

1,

0),

tf9

=

(0,

1,

1, 1), /?1 0

=

(0,

1,

1,

2),

Я и

= (0(, 1,

2,

0),

Я 1 2 =

(0, 1, 2,

1),

Я 1 3 =

(0, 1, 2,

2),..tf1 4 =

(0, 1.-І2, 3) =

/*.

5*

67

/И-структура векторов различимости при п = 4 приведена

на

рис. 9. Элементы М-структуры

относительно операции

сложения

образуют полугруппу

R*,

представленную

при л =

4 в табл.

10.

Т а б л и ц а

10

и

QR

Ri

R*

R3

R<

Rb

R*

Ri

Rs

R»

Rio

Ru

Ru

R13

IR

о*

QR

Ri

R*

R3

R,

R*

R*

R,

Ra

R»

Rio

Ru

Ru

R13

IR

я,

Ri

R,

R,

R,

Ri

R,

R,

Rw

Rio

Rio

{R

'R

IR

R2

Rt

R,

Rn

'R

Ru

Ri,

Ы Ru

Ru

'R

IR

Rs ' R* R13

FR

IR

R13

IR

[R

<R

R13

IR

R*

R*

IR

IR

JR

U

IR

и

>R

IR

IR

R*

R7

R-

Ru

Ru

Ru

IR

R13

IR

R.

Rn

R-,

IR

Ru

LR

'R

R\z

IR

IR

Ri

Ri

IR

LR

*R

IR

!R

'R

IR

Rs

Ra

Rio

Ru

Ru

!R

IR

IR

R*

R*

Rio

IR

R12

RIS

IR

Rio

Rio

IR

'R

IR

IR

Ru

Ru

LR

IR

IR

Rl2

R12

IR

IR

Rj3

R13

<R

Введем понятия покрытия в М -структуре.

Определение 3.1.

Множество векторов

различимости {Rlt R2, ...

Rk} называется

покрытием в /И-ст.руктуре,

если

одновременно

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

2)

для всех

1 < ! i,

j < ; k, і Ф j , не имеет место R( <;

R/;

3)

Rit \JRi,

U ... U Re ФЫ для всех it =

~k

и т <

к.