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

большим

i

имеется момент угадывания (т.е. найдется такое

j

, что

α

(

j

+

+1) =

β

(

j

)

). Скажем также, что язык

L

угадывается с интервалом

T

,

если каждое слово языка угадывается с интервалом

T

.

Язык назовем

частично угадываемым в узком смысле

, если най-

дется процесс угадывания (2) с конечным интервалом угадывания.

Степень и интервал угадывания для путей определяется так же, как и

для языков.

Легко заметить, что из частичной угадываемости в узком смысле

следует частичная угадываемость в широком смысле. Причем в ка-

честве степени угадывания можно взять число

1

/T

(а также любое

меньшее число), где

T

— интервал угадывания.

Обратное утверждение неверно. Так, последовательность вида

(0

n

(0

1)

n

)

будет угадана в широком смысле автоматом, выдающим

константу 0 (со степенью 0,5), но для любого угадывающего устрой-

ства в ней может встречаться произвольное число неугаданных подряд

символов. Таким образом, возникает задача исследования угадывае-

мости (в широком или узком смысле) языков и множеств путей. Далее

наметим класс языков и множеств путей, для которых рассмотрим эту

задачу.

План дальнейшего исследования задачи угадывания.

Вернемся к

леммам 1 и 2. Согласно этим леммам, намечается следующий есте-

ственный класс множеств путей и языков, для которых можно рассмо-

треть задачи угадывания:

1) множества путей вида

R

(

Q

)

и языки

L

(

q

0

, Q

)

для сильно связ-

ного орграфа

Q

;

2) множества путей вида

R

(

Q, Q

0

)

и языки

L

(

q

0

, Q, Q

0

)

, где

Q

0

сильно связное множество вершин орграфа

[

Q

]

(напомним, что

[

Q

]

— краткое обозначение орграфа с множеством вершин

Q

);

3) объединения множеств путей и языков, указанных в предыду-

щем пункте.

Перечисленные задачи изучим последовательно.

Задача угадывания для множеств путей в сильно связных гра-

фах.

Множества

R

(

Q

)

.

Рассмотрим сильно связный граф

[

Q

]

. Напо-

мним, что он назван совершенным, если из каждой вершины выходят

два ребра (и несовершенным — в противном случае). Ясно, что для

совершенного орграфа множество

R

(

Q

)

не допускает частичного уга-

дывания. Для несовершенного орграфа — положение иное.

Теорема 1.

Пусть дан сильно связный несовершенный орграф

[

Q

]

.

Тогда множество

R

(

Q

)

частично угадываемо

,

причем интервалом

угадывания будет число

n, n

=

|

Q

|

. Это верно и для языка

L

(

q

0

, Q

)

.

Необходимый автомат-угадчик будет построен в ходе доказатель-

ства, которое начнем с доказательства леммы.

8

ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2