3 / 13
Лемма 1.
Для любого пути
r
=
a
1
→
a
2
→
. . .
множество
Q
0
силь-
но связно. Существует такой номер
m,
что все вершины
a
i
, i > m,
лежат в множестве
Q
0
.
Доказательство леммы (весьма простое) опускаем. Итак, в любом
орграфе любой (бесконечный вправо) путь после отбрасывания не-
скольких его начальных вершин лежит в сильно связном подграфе
(предельном множестве пути). Этот простой факт окажется весьма
полезным для основной цели настоящей работы (задачи угадывания).
Возьмем произвольное сильно связное множество
Q
0
⊂
Q
и обо-
значим через
R
(
Q, Q
0
)
множество всех путей с предельным множе-
ством
Q
0
. Положим
R
(
q
0
, Q, Q
0
) =
R
(
Q, Q
0
)
∩
R
(
q
0
, Q
)
. Приведенная
ниже лемма немедленно следует из леммы 1.
Лемма 2.
Справедливо равенство
R
(
Q
) =
∪
Q
0
R
(
Q, Q
0
)
(объедине-
ние по всевозможным сильно связным подмножествам
Q
0
орграфа)
.
Языки и орграфы.
Используем только языки в алфавите
{
0
,
1
}
.
Рассмотрим множество
{
0
,
1
}
∞
,
состоящее из всех бесконечных по-
следовательностей
α
=
α
(1)
α
(2)
. . . ,
где
α
(
i
)
∈ {
0
,
1
}
, i
= 1
,
2
, . . .
; они
называются
словами
. Удобно полагать, что в каждый момент времени
n
подается символ
α
(
n
)
слова
α
. Любое подмножество
L
⊂ {
0
,
1
}
∞
называется
языком
(в алфавите
{
0
,
1
}
). Применяются также термины
“сверхслово”, “
ω
-слово”, “сверхязык”, “
ω
-язык”. Здесь выбраны более
короткие названия.
Для создания языков используем орграфы
G
= (
Q, E
)
со следу-
ющим свойством: из каждой вершины исходят либо два ребра, либо
одно. Если из каждой вершины исходят два ребра, назовем граф
со-
вершенным
, если имеются вершины, из которых выходит единствен-
ное ребро, то назовем граф
несовершенным
. Пусть дано отображение
f
:
E
→ {
0
,
1
}
. Величину
f
(
a, b
)
назовем
f
-
меткой
на ребре
a
→
b
.
Потребуем, чтобы
f
(
a, b
)
6
=
f
(
a, c
)
в случае, когда из вершины ис-
ходят два ребра
a
→
b
и
a
→
c
. Полученный объект (
размеченный
орграф
) обозначим через
G
= (
Q, E, f
)
. Если фиксирована вершина
q
0
, то запишем
G
= (
Q, E, f, q
0
)
.
Каждому пути
a
1
→
a
2
→
. . .
поставим в соответствие слово
α
=
α
(1)
α
(2)
. . .
, где
α
(
i
) =
f
(
a
i
, a
i
+1
)
,
i
= 1
,
2
, . . .
Получим ото-
бражение
R
(
Q
)
→ {
0
,
1
}
∞
.
При таком отображении образы мно-
жеств
R
(
Q
)
, R
(
Q, Q
0
)
и
R
(
q
0
, Q, Q
0
)
обозначим через
L
(
Q
)
, L
(
Q, Q
0
)
и
L
(
q
0
, Q, Q
0
)
. В случае совершенного графа отображение
R
(
q
0
, Q
)
→
→ {
0
,
1
}
∞
взаимно-однозначно.
Ограничимся графами, в которых полустепень исхода каждой вер-
шины не превосходит двух. Это обусловлено тем, что с графом свя-
зываем язык с алфавитом из двух символов. Рассмотрение графов без
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2
5