6 / 13
большим
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