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

Лемма 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