4 / 13
указанного свойства (при сохранении указанного алфавита) потребо-
вало бы существенного изменения (и усложнения) теории.
Угадывание языков и путей.
Проблема угадывания слова (в ал-
фавите
{
0
,
1
}
) состоит (неформально) в следующем: зная первые
n
символов слова
α
∈
L
(слово
α
(1)
α
(2)
. . . α
(
n
)
), угадать следующий
символ
α
(
n
+ 1)
. Обозначим через
β
(
n
)
“прогноз” относительно того,
каким будет (
n
+1
)-й символ
α
(
n
+1)
слова
α
. Если
α
(
n
+1) =
β
(
n
)
для
некоторого
n
, то можно утверждать, что
n
-й символ слова
α
правильно
угадан
(или угадан), число
n
назовем
моментом правильного угады-
вания
(или моментом угадывания) этого символа. Запишем цепочку
прогнозов:
β
(1)
, . . . , β
(
n
)
, . . .
(1)
Таким образом, процесс угадывания слова можно записать в виде
α
(1)
, β
(1)
, . . . α
(
n
)
, β
(
n
)
, . . .
(2)
Процесс угадывания языка
L
задается цепочками вида (1) для каждого
слова
α
∈
L
.
Задача угадывания пути в орграфе — зная пройденные вершины
a
1
, . . . , a
k
пути, предсказать следующую вершину
a
k
+1
. Если зафик-
сировать вершину
q
0
орграфа, то пути, выходящие из вершины
q
0
,
отождествляются со словами в алфавите и тем самым задачи угады-
вания слов и путей оказываются эквивалентными.
Несколько модифицируем определение, полагая, что угадыва-
ние может происходить не в каждый момент, а в моменты времени
k
1
, k
2
, . . .
Таким образом, в цепочке (1) будут отсутствовать некоторые
прогнозы; условимся писать черточки на этих позициях (например,
запись
0
,
1
,
−
,
0
, . . .
будет означать, что
β
(1) = 0
, β
(2) = 1
, в момент 3
угадывания нет и т.д.).
В целях реализации угадывания путей на орграфе поставим в
соответствие некоторым (возможно, не всем) ребрам
a
→
b
метки
g
(
a, b
)
∈ {
0
,
1
}
; назовем их
g
-метками. Если, двигаясь по пути, дойти
до вершины
a
k
данного пути и на ребре
a
k
−
1
→
a
k
считать
g
-метку
g
(
a
k
−
1
, a
k
)
, то можно спрогнозировать, что следующей будет такая
вершина
a
k
+1
, что
f
(
a
k
, a
k
+1
) =
g
(
a
k
−
1
, a
k
)
. Разумеется, придется уга-
дывать множества путей
R
⊂
R
(
Q
)
, а не только отдельные пути.
Соответственно, если речь идет об угадывании слова, то прогно-
зируем, что следующей буквой слова будет
g
(
a
k
−
1
, a
k
)
. Таким обра-
зом, указанная выше “угадывающая функция”
F
задается равенством
F
(
α
(1)
α
(2)
. . . α
(
k
)) =
g
(
a
k
−
1
, a
k
)
.
Итак, роль меток на ребрах такая:
f
-метки позволяют установить
биекцию между словами и путями (в этом месте рассматриваются
6
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2