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

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

которого (желательно, достаточно большого) множества моментов

их поступления. Частота моментов удачного угадывания — основная

характеристика процесса. Задача частичной угадываемости языков

изучена в работе [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