Для цепочек допустимы следующие действия
а) конкатенация (сцепление) цепочек:
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.