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

указанного свойства (при сохранении указанного алфавита) потребо-

вало бы существенного изменения (и усложнения) теории.

Угадывание языков и путей.

Проблема угадывания слова (в ал-

фавите

{

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