yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Дискретная математика

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

 

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

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

x = aba, y = cab;     xy = abacab;

б) возведение цепочек в степень:

x=ab; (х)^1 = ab; (х)^2 = (ab)^2 = abab; (х)^3 = (ab)^3 = ababab;

любая цепочка в нулевой степени равна @:  (x)^0 = @.

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

 

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

Итерация - множество полученное от объединения всех степеней  алфавита, включая и нулевую: V* = U V^i (i ї No ).

Усеченная итерация (обозначается V+) не включает нулевую  степень алфавита т.е. пустую цепочку: V+ = U^i(i ї N).

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

V+ = V х V* = V* x V.

 

 

7