2 / 13
начиная с некоторого места), требуя угадать символы лишь для не-
которого (желательно, достаточно большого) множества моментов
их поступления. Частота моментов удачного угадывания — основная
характеристика процесса. Задача частичной угадываемости языков
изучена в работе [2]. В частности, в ней введена упомянутая харак-
теристика, названная
степенью угадывания
, и дана ее оценка для
некоторых естественных классов языков.
В настоящей работе, во-первых, модифицировано (упрощено) по-
нятие частичного угадывания, во-вторых, изложены методы частич-
ного угадывания для класса языков, рассмотренных в работе [3]. Эти
методы основаны на ином подходе к таким задачам; как следствие,
они проще тех, которые рассмотрены в работе [3] и легко реализуемы.
Сопоставлены результаты, полученные в данной статье, с результа-
тами, приведенными в работе [3]. В изложении использованы лишь
элементарные понятия, связанные с графами и автоматами.
Основные понятия. Постановка задачи.
Приведем необходимые
сведения о графах и языках, а также основную задачу — угадывание
языков и множеств путей в графах.
Орграфы.
Рассмотрим конечные ориентированные графы (оргра-
фы) вида
G
= (
Q, E
)
, где
Q
— множество вершин;
E
— множество
ориентированных ребер; ребра запишем в виде
a
→
b
. Допустимы
петли
a
→
a, a
∈
Q
. Для любого множества
Q
0
⊂
Q
обозначим через
[
Q
0
]
подграф
(
Q
0
, E
0
)
, E
0
— множество всех ребер графа
(
Q, E
)
, верши-
ны которых принадлежат множеству
Q
0
. В частности, граф
G
= (
Q, E
)
обозначим через
[
Q
]
, в том случае, когда это не будет вызывать неод-
нозначности. Граф, содержащий хотя бы одно ребро, назовем нетри-
виальным.
Граф называется
сильно связным
, если для любых двух его вершин
a
1
и
a
2
найдется путь из
a
1
в
a
2
и путь из
a
2
в
a
1
. Если
G
= (
Q, E
)
—
произвольный орграф, то множество
Q
0
⊂
Q
назовем сильно связ-
ным, если подграф
[
Q
0
]
является сильно связным. Максимальный (по
включению) сильно связный подграф графа назовем сильно связной
компонентой. Пути (бесконечные вправо) будем записывать в виде по-
следовательности вершин
a
1
→
a
2
→
. . .
Множество всех таких путей
обозначим через
R
(
Q
)
, а множество путей, исходящих из вершины
q
0
, — через
R
(
q
0
, Q
)
.
Конечный путь
a
i
→
. . .
→
a
j
, j > i,
назовем
отрезком пути
a
1
→
a
2
→
. . .
Определение 1.
Множество вершин
Q
0
⊆
Q,
встречающихся на
пути
r
=
a
1
→
a
2
→
. . .
бесконечно много раз, назовем предельным
множеством данного пути.
Используем обозначение
Q
0
= lim
r
, или
Q
0
= lim
a
i
.
4
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2