Слова в однобуквенном алфавите.

— алфавит, состоящий из одной буквы называемой вертикальной палочкой. Обозначим через N множество всех слов в однобуквенном алфавите . Множеству N принадлежат пустое слово, обозначаемое символом 0, слова д. Если — слово в алфавите , то и — тоже слово в этом алфавите.

Два элемента из N называют равными и пишут гаг если они равны как слова (равны графически). Если слова не равны, то пишут

ОПРЕДЕЛЕНИЕ. Пусть — произвольные слова в алфавите . Композиция слов называется суммой гаг и и обозначается гаг Операция называется операцией сложения.

Например, композицией слов является слово . Следовательно, .

Композиция любого слова из N и пустого слова есть, по определению, слово Следовательно,

Выше отмечалось, что композиция слов обладает свойством ассоциативности. В частности, для любых элементов гаг и из N верно равенство гаг или, поскольку

Свойство ассоциативности композиции слов позволяет определить сумму трех слагаемых и более:

ОПРЕДЕЛЕНИЕ. Произведением двух слов тип () называется слово, равное сумме слагаемых, каждое из которых равно . Кроме того, полагаем

Произведение слов тип обозначим . Операция называется умножением слов. Таким образом,

Например, для любого m из N имеем: