9 / 13
ребро
a
i
→
a
i
+1
содержится в подграфе
[
Q
0
]
, то на этом ребре имеем
прогноз (удачный, либо неудачный) относительно следующей верши-
ны. Если это ребро не входит в подграф
[
Q
0
]
, то прогноз отсутствует.
В частности, если указанный путь взят из
R
(
Q, Q
0
)
, то начиная с неко-
торого момента прогнозы (возможно, неудачные) будут происходить
уже без прерываний.
Выше речь шла о путях; изложенное можно перенести на поро-
жденные ими языки.
Частичное угадывание объединения языков.
Рассмотрим язы-
ки
L
s
=
L
(
q
0
s
, Q
s
, Q
0
s
)
, s
= 1
, . . . , m,
описанные выше. Пусть каждый
язык
L
s
=
L
(
q
0
s
, Q
s
, Q
0
s
)
частично угадываем (с некоторым интер-
валом угадывания
T
s
); таким образом, все орграфы
[
Q
0
s
]
несовер-
шенны. Предположим также, что на каждом подграфе
[
Q
0
s
]
постро-
ены
g
s
-метки, задающие угадывание. Следовательно, имеем автома-
ты
G
s
= (
Q
s
, E
s
, f
s
, g
s
, q
s
0
)
.
Рассмотрим язык
L
=
∪
m
s
=1
L
(
q
0
s
, Q
i
, Q
0
i
)
.
Цель — построить алгоритм, позволяющий угадать этот язык (и оце-
нить интервал угадывания).
Зафиксируем слово
α
=
α
(1)
α
(2)
. . .
и постараемся построить для
него цепочку прогнозов с положительным интервалом угадывания.
Каждый автомат
G
s
с помощью своих
f
s
- и
g
s
-меток дает процесс
угадывания (цепочка (2)), а также цепочку прогнозов (цепочка (1)),
которая в рассматриваемом случае принимает вид
β
s
(1)
, β
s
(2)
, . . .
(3)
Трудность в использовании этих прогнозов заключается в следу-
ющем. В каждый момент времени угадывающее лицо имеет в своем
распоряжении несколько начальных букв угадываемого слова; однако
эти начальные буквы слова не позволяют судить о том, какому из язы-
ков
L
s
принадлежит указанное слово. Поэтому процедура угадывания
слова окажется не совсем простой.
Идея этой процедуры следующая. На каждый автомат подаем ука-
занное слово
α
=
α
(1)
α
(2)
. . .
Каждый автомат дает цепочку прогно-
зов относительно букв слова (напомним, что эта работа может иметь
“прерывистый” характер, т.е. в некоторые моменты угадывание мо-
жет и не происходить). Возьмем достаточно большое число
R
и из
всех прогнозов, выданных автоматами в момент
k
, возьмем прогноз,
принадлежащий автомату, который проработал (угадывал, возможно,
не всегда успешно) без пропусков в предыдущие
R
моментов. (Если
имеется несколько таких автоматов, то возьмем из них автомат с наи-
меньшим номером.) Это и есть искомый прогноз относительно следу-
ющей буквы слова
α
.
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2
11