Языки и трансляции. Мартыненко Б.К. - 32 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

31
Итак, имеем
dRb, cRb или по симметричности — bRс и, наконец, cRa. Из
dRb, bRс и cRa по транзитивности получаем dRa. Но это противоречит
предыдущему выводу
d
R
a.
Отдельные множества [
a] для a∈S называются классами эквивалентности.
Ясно, что элементы
a и b находятся в одном и том же множестве — классе
эквивалентности тогда и только тогда, когда они эквивалентны, т.е. когда
aRb.
Определение 3.5. Индекс отношения эквивалентности R, заданного на
множестве
S, есть число образуемых им классов эквивалентности.
Замечание 3.1. Очевидно, что если S — конечно, то индекс отношения
эквивалентности k не может быть бесконечным. В общем случае, когда S — бесконеч-
но, k может быть как конечным, так и бесконечным.
Рассмотрим конечный автомат, приведённый в примере 3.1. Определим
отношение
R на множестве {0, 1}
*
следующим образом: (x, y) ∈R тогда и толь-
ко тогда, когда δ(
q
0
, x) = δ(q
0
, y). Отношение R рефлексивно, симметрично и
транзитивно, т.е.
R — отношение эквивалентности. Отношение R делит
множество {0, 1}
*
на четыре класса эквивалентности, соответствующие четы-
рем состояниям автомата. Кроме того, если
xRy, то для всех z∈{0, 1}
*
имеет
место
xzRyz, поскольку δ(q
0
, xz) = δ(δ(q
0
, x), z) = δ(δ(q
0
, y), z) = δ(q
0
, yz). Такое
отношение эквивалентности называется
правоинвариантным.
Теорема 3.2. Следующие три высказывания эквивалентны:
1) язык L ⊆ Σ
*
принимается некоторым конечным автоматом;
2) язык L есть объединение некоторых классов эквивалентности право-
инвариантного отношения эквивалентности конечного индекса;
3) пусть отношение эквивалентности R определяется следующим образом:
xRy тогда и только тогда, когда для всех z ∈ Σ
*
цепочка xz ∈L точно тогда, когда
цепочка yz∈L. Отношение R имеет конечный индекс.
Доказательство.
1)
→ 2). Предположим, что язык L принимается некоторым конечным
автоматом
M
’
= (Q
’
, Σ
’
, δ
’
, q
0
’, F
’
). Пусть R
’
— отношение эквивалентности,
определяемое следующим образом:
xR
’
y тогда и только тогда, когда δ
’
(q
0
’, x) =
δ
’
(q
0
’, y). Отношение R
’
правоинвариантно, поскольку, если δ
’
(q
0
’, x) = δ
’
(q
0
’, y), то
для любого z∈Σ
*
имеем δ
’
(q
0
’, xz) = δ
’
(δ
’
(q
0
’, x), z) = δ
’
(δ
’
(q
0
’, y), z) = δ
’
(q
0
’, yz).
Индекс отношения
R
’
конечен, поскольку, самое большее, он равен числу
состояний fa
M
’
. Кроме того, язык L есть объединение тех классов эквива-
лентности, которые включают элемент
x, такой, что δ
’
(q
0
’, x) = p, где p∈ F
’
.
2)
→ 3). Покажем сначала, что любое отношение эквивалентности R
’
, для
которого справедливо высказывание 2, является уточнением отношения
R, т.е.
каждый класс эквивалентности
R
’
целиком содержится в некотором классе
эквивалентности
R. Если это так, то индекс отношения R не может быть
больше индекса отношения
R
’
. Индекс отношения R
’
, как было показано,
конечен. Следовательно, индекс отношения
R тоже конечен.

Страницы