11 / 13
J
1. Зафиксируем отрезок длиной
R
и рассмотрим точки из него,
в которых выполнено неравенство
Φ(
k
)
<
Φ(
k
+ 1)
. Докажем, что
число таких точек не превосходит
m
. Допустим противное. Поскольку
функция
Φ(
k
)
принимает не более чем
m
значений, а число скачков
превосходит
m
, найдутся такие
k, l
, что
Φ(
k
)
<
Φ(
k
+ 1)
,
Φ(
l
)
<
Φ(
l
+
+1)
, k < l,
Φ(
k
) = Φ(
l
) =
i
для некоторого
i
. Из определения функции
Φ
следует, что
[
k
−
R, k
]
⊂
D
i
и
[
l
−
R, l
]
⊂
D
i
. Однако
l
−
R
6
k
,
поэтому
[
k
−
R, l
]
⊂
D
i
. В частности,
[
k
+ 1
−
R, k
+ 1]
⊂
D
i
. В
соответствии с определением функции
Φ
,
Φ(
k
+ 1)
6
i
, т.е.
Φ(
k
+
+ 1)
6
Φ(
k
)
. Противоречие.
2. Рассмотрим точки скачка, в которых выполнено неравенство
Φ(
k
)
>
Φ(
k
+ 1)
. Докажем, что число таких точек не превосходит
m
.
Здесь рассуждения аналогичны предыдущим; тем не менее проведем
их. Допустим противное и каждому скачку поставим в соответствие
пару
(Φ(
k
)
,
Φ(
k
+ 1))
. Тогда найдутся такие
k, l
, что
Φ(
k
)
>
Φ(
k
+
+ 1)
,
Φ(
l
)
>
Φ(
l
+ 1)
, k < l,
Φ(
k
+ 1) = Φ(
l
+ 1) =
i
для некоторого
i
.
Из определения функции
Φ
следует, что
[
k
+ 1
−
R, k
+ 1]
⊂
D
i
и
[
l
+ 1
−
R, l
+ 1]
⊂
D
i
. Однако
l
+ 1
−
R
≤
k
+ 1
, поэтому
[
k
+ 1
−
R, l
+
+1]
⊂
D
i
. В частности,
[
l
−
R, l
]
⊂
D
i
. Согласно определению функции
Φ
,
Φ(
l
)
6
i
, т.е.
Φ(
l
)
6
Φ(
l
+ 1)
. Противоречие.
Учитывая пп. 1 и 2 получаем утверждение леммы 6.
I
Лемма 7.
В любой цепочке
{
s, s
+1
, . . . , s
+
R
}
существует отрезок
длиной
[
R/
(2
m
)]
, на котором функция
Φ
постоянна.
Доказательство леммы 7 следует из леммы 6.
Вернемся к доказательству второго утверждения теоремы 2.
Возьмем отрезок натуральных чисел длиной
R
, в нем отрезок дли-
ной
[
R/
(2
m
)]
, указанный в лемме 7; пусть этот отрезок есть
{
l, l
+
+ 1
, . . . , l
+
r
}
,
r
= [
R/
(2
m
)]
.
На этом отрезке функция
Φ
принимает
постоянное значение
i.
Поэтому цепочка прогнозов (4) принимает вид
β
i
(
l
)
, β
i
(
l
+1)
, . . . , β
i
(
l
+
r
)
,
т.е. совпадает с цепочкой прогнозов, полу-
ченных автоматом
G
i
. Напомним, что
[
R/
(2
m
)]
> T
i
. Следовательно,
на указанном отрезке имеется момент правильного угадывания для
автомата
G
i
. Теорема 2 доказана.
I
Следствие 2.
Язык вида
L
=
∪
m
i
L
(
q
i
0
, Q
i
, Q
0
i
)
является частич-
но угадываемым тогда и только тогда, когда каждый подграф
[
Q
0
i
]
несовершенен, причем угадывание происходит с интервалом
max
{|
Q
0
i
|
, i
= 1
, . . . , m
}
.
Заключение.
Как было отмечено выше, изучение частичной уга-
дываемости языков было начато в работах [2, 3]. Теорема 1 (критерий
частичной угадываемости языка
L
(
q
0
, Q, Q
0
)
) была доказана в рабо-
те [3]. При этом и терминология, и методы, принятые в указанной
работе, существенно отличались от тех, какие были использованы в
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2
13