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

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