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

ребро

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