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

UptoLike

ВУЗ: 

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

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

Рубрика: 

30
Предположим, что на входе автомата находится цепочка 110101.
Поскольку δ(
q
0
, 1) = q
1
, а δ(q
1
, 1) = q
0
и q
0
∈F, то цепочка 11 находится в языке,
распознаваемом данным конечным автоматом, т.е. в
T(M). Но мы интересуемся
всей входной цепочкой. Сканируя остаток 0101 входной цепочки, автомат
переходит последовательно в состояния
q
2
, q
3
, q
1
, q
0
. Поэтому δ(q
0
, 110101) = q
0
и потому вся цепочка 110101 тоже находится в
T(M).
Легко показать, что
T(M) есть множество всех цепочек из {0, 1}
*
, содер-
жащих чётное число нулей и чётное число единиц. В частности,
ε∈T(M).
§ 3.2. Отношения эквивалентности
и конечные автоматы
Напомним несколько понятий, относящихся к бинарным отношениям,
которые потребуются в дальнейшем для описания свойств конечных
автоматов.
Определение 3.3. Бинарное отношение R на множестве S есть множество
пар элементов
S.
Если (
a, b) ∈R, то по-другому это записывают как aRb. Нас будут интересо-
вать отношения на множествах цепочек над конечным алфавитом.
Определение 3.4. Пусть s, t, u∈S. Говорят, что бинарное отношение R на
множестве
S рефлексивно, если имеет место sRs; симметрично, если sRt влечет
tRs; транзитивно, если из sRt и tRu следует sRu.
Отношение, которое рефлексивно, симметрично и транзитивно, называется
отношением эквивалентности.
Следующая теорема говорит о важном свойстве отношений эквивалент-
ности.
Теорема 3.1. Если R — отношение эквивалентности на множестве S, то S
можно разбить на k непересекающихся подмножеств, называемых классами
эквивалентности, так что aRb тогда и только тогда, когда a и b находятся в
одном и том же подмножестве.
Доказательство. Определим [a] как {b | aRb}. Для любых a и b из множе-
ства
S имеет место одно из двух соотношений: либо [a] = [b], либо [a] ∩ [b] = ∅.
Начнём доказательство от противного.
Пусть [
a] ≠ [b] и [a] ∩ [b] ≠ ∅. Из [a] ≠ [b] следует, что существует d∈S,
такое, что
d∉[a] и d∈[b] или, что то же самое, d
R
a и dRb.
Кроме того, из [
a] ∩ [b] ≠ ∅ следует, что существует с ∈ S, такое, что с∈[a]
и
с ∈[b] (рис. 3.3) или, что то же самое, cRa и cRb.
Рис. 3.3.Рис. 3.3.

Страницы