Previous Page  5 / 13 Next Page
Information
Show Menu
Previous Page 5 / 13 Next Page
Page Background

Рис. 1. Путь

a

b

c

барьер

пути, выходящие из фиксированной верши-

ны

q

0

);

g

-метки дают прогноз относительно

очередной буквы слова (при условии, что

известны предшествующие буквы).

Для того чтобы сделать процесс угады-

вания наглядным, введем следующее поня-

тие. Назовем

барьером

двухреберный путь

a

b

c

(рис. 1), удовлетворяющий усло-

вию

g

(

a, b

) =

f

(

b, c

)

. Если дано слово и соответствующий ему путь,

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

случае, когда путь прошел через барьер.

Орграф с метками

f

:

E

→ {

0

,

1

}

и

g

:

E

→ {

0

,

1

}

обозначим

через

G

= (

Q, E, f, g

)

. Если фиксирована вершина

q

0

, то запишем

G

= (

Q, E, f, g, q

0

)

1

. Напомним, что

g

-метки заданы, возможно, не

на всех ребрах. Итак, автомат

G

= (

Q, E, f, g

)

служит и для задания

языка (по данному множеству путей), и для угадывания этого языка.

Степень угадывания и интервал угадывания.

Введем понятие,

позволяющее оценить “качество” данного процесса угадывания. Оно

было введено в работе [2]; воспроизведем его, используя приведенную

выше терминологию (отметим, что она отличается от терминологии,

принятой в работе [3]).

Возьмем язык

L

. Пусть дан некоторый процесс угадывания; таким

образом, для любого слова

α

=

α

(1)

α

(2)

. . .

, взятого из процесса

L

,

указана “угадывающая процедура” (2) и цепочка прогнозов (1).

Возьмем слово

α

и соответствующую ему цепочку прогнозов (1).

Для каждого

n

>

1

обозначим через

r

(

n

)

число удачных угадываний на

временн´ом промежутке

1

, . . . , n

; другими словами,

r

(

n

) =

|{

k

:

α

(

k

+

+1) =

β

(

k

)

}

, k

6

n

|

.

Степень угадывания

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

ством

lim

r

(

n

)

/n, n

→ ∞

. Степень угадывания языка

L

— такое число

σ

, что любое слово из процесса

L

угадывается со степенью, не мень-

шей

σ

. Как следует из определения, если

σ

— степень угадывания, то

таковым будет и любое число

σ

1

< σ

.

Язык назовем

частично угадываемым в широком смысле

, если су-

ществует процесс угадывания

(2)

с ненулевой степенью угадывания.

Далее модифицируем эти понятия следующим образом (снова исполь-

зуем цепочку прогнозов (1)).

Скажем, что слово

α

частично угадывается с

интервалом угады-

вания

T

, если на любом промежутке

i, i

+ 1

, . . . , i

+

T

с достаточно

1

В другой терминологии имеем неинициальный и, соответственно, инициальный

автомат с входной функцией

f

и выходной функцией

g

.

ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2

7