Лекция № 2

Тема: Действия с цепочками

Цель: Ознакомить с понятием вектора, цепочки и действиями, выполняемыми с цепочками.

План

1. Прямое произведение множеств.

2. Действия с цепочками. (Самостоятельное изучение).

3. Число элементов множеств.

1. Прямое произведение множеств

Прямым или декартовым произведением множеств называется множество, элементами которого являются векторы, составленные из элементов перемножаемых множеств: первые компоненты векторов – элементы первого множества, вторые – второго и т.д.

Для двух множеств процедура имеет вид:

А×В = {(а,b)|аєА и bєВ}.

А = {a,b,c,...,h}; В = {1,2,3,...,8};

D = A×B = {(a,1);(a,2);(a,3);...(h,8)}.

Допускается запись D = A×B = {a1;a2;a3;...h8}.

Вектор – упорядоченный набор элементов. Элементы, образующие вектор, называются координатами или компонентами вектора. Число координат называется длиной или размерностью вектора. В отличии от элементов множества координаты вектора могут быть одинаковыми.

Пример:

В = (0,3,5,3) вектор размерности 4.

С = (0,3,3,5) – вектор размерности 4.

Векторы В и С различны, т.к. порядок следования координат различный.

Операция прямого произведения множеств многоместна (перемножать можно несколько множеств) и не коммутативна. В качестве сомножителей может выступать одно и то же множество, т.е. множество можно возводить в п – ую степень.

В качестве примера рассмотрим случай, когда элементами множества являются символы, например: V = {a, b, c}. Такое множество будем называть алфавитом. При возведении этого множества в квадрат получим новое множество, состоящее из двухсимвольных цепочек или слов (элементы – векторы записываются без скобок и разделяющих запятых).

V² = V×V = {aa, ab, ac, ba,...cc}.

При возведении алфавита в куб (последнее множество умножаем на V)

получаем трехсимвольные слова – цепочки и т. д. Алфавит в нулевой степени представляет собой множество, состоящее из одного элемента – пустой цепочки (обозначение ξ – эпсилон):

V⁰ = {ξ}.

Длина цепочки равна количеству элементов, образующих эту цепочку.

Пустую цепочку ξ можно вставить в любое место других цепочек, не изменяя их:

|a|=1; |aba| = 3; |abξa| = 3; |ξ| = 0.

2. Действия с цепочками

Для цепочек допустимы следующие действия:

• Конкатенция (сцепление) цепочек:

х = aba, y = cad, xy = abacad;

• Возведение цепочек в степень:

Х = ab; x¹ = ab; x² = abab; x³ = (ab)³ = ababab;

Любая цепочка в нулевой степени равна ξ:

х⁰ = ξ.

Нельзя отождествлять пустое множество С = {} и множество, содержащее один элемент – пустую цепочку В = {ξ}.

Все множество цепочек, которые могут быть созданы в заданном алфавите, можно представить таким понятием, как итерация алфавита.

Итерация – множество, полученное в результате объединения всех степеней алфавита, включая и нулевую:

Vⁿ = U Vⁱ.

(i є N₀)

Усеченная итерация (обозначается V⁺) не включает нулевую степень алфавита, т.е. пустую цепочку:

V⁺ = UVⁱ.

(iєN)

Итерацию и усеченную итерацию связывает следующая формула:

V⁺ = V×Vⁿ = Vⁿ×V.