Синтез цифровых автоматов. Захаров Н.Г - 132 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

131
черта после х означает «таких, что», т. е. Х – множество элементов таких, что они
обладают свойством Q.
Множество Х называется
подмножеством множества Y (иначе – Х входит в
Y), если и только если каждый элемент множества Х принадлежит множеству Y. Обо-
значение: X
⊆ Y или Y ⊇ X.
Например, если каждый элемент множества Х принадлежит множеству Y, то
записывают X
⊂ Y и говорят, что Х является подмножеством множества Y. Отноше-
ние
⊂ называется включением.
Операции над двумя множествами Х и Y:
1. Объединение Х
∨ Y.
2. Пересечение Х
∧ Y.
3. Дополнение
Х и Y .
4. Разность Х \ Y.
5. Произведение Х
× Y.
Декартовым или прямым
произведением Х × Y называется множество всех
упорядоченных пар, первый и второй компоненты которых принадлежат соответст-
венно множествам X и Y. Множество Х называется первым, а множество Y вторым
сомножителем произведения Х и Y. Меняя ролями множества Х и Y, получаем декар-
тово произведение Y
× X, которое отлично от декартова произведения Х × Y, если
Х
≠ Y.
Любое подмножество Р
⊆ Х × Y произведения множеств Х и Y называется би-
нарным соответствием
из Х в Y. При этом множество Х называется областью от-
правления
, а множество Y – областью прибытия соответствия Р.
Иногда для определения операции произведения множеств используют понятие
кортежа (вектора). Вместе с понятием кортежа вводится понятие компонента (ко-
ординаты).
Регулярные и нерегулярные множества. Класс множеств цепочек над конеч-
ным словарем V называют
регулярными множествами.
Пусть V1 и V2 – множества цепочек, тогда на этих множествах цепочек можно
определить следующие
операции:
1. Объединение V
1
и V
2
= {α | α ∈ V
1
} или α ∈ V
2
.
2. Конкатенация (произведение, склеивание): V
1
⋅ V
2
= {αβ | α ∈ V
1
, β ∈ V
2
}.
Знак конкатенации обычно опускается.
Например,
V
1
= {abc, ba}, V
2
= {b, cb}. V
1
V
2
= {abcb, abccb, bab, bacb}.
Обозначим через V
n
произведение n множеств V, т. е. V
n
= VV ... V при V
0
= {ε},
где
ε – пустая цепочка.
Например,
V
1
= {abc, ba}, V
1
2
= {abcabc, abcba, baba, baabc}.
3. Итерация: V* = V
0
∨ V
1
∨ V
2
∨ ...
Например,
V = {a, bc}, V* = {ε, a, bc, aa, abc, bc, bc, bca, aaa, aabc, ... }.
Правила для класса регулярных множеств над конечным словарем V:
1.
∅ – регулярное множество;
2. {
ε} – регулярное множество;
3. (
∀а ∈ V) {a} – регулярное множество;
4. Если А и В – регулярные множества, то регулярны:
-
объединение А ∨ В;
-
конкатенация АВ;

Страницы