5 / 13
Рис. 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