Словарные операторы

Рассмотрим конечный алфавит , составленный из букв : .

Элементы декартового произведения называют словами длины в алфавите : . При имеем пустое слово, которое обозначается . Множество всех слов в алфавите обозначается : .

Длину слова обозначим . Например, , .

Пусть и – произвольные слова из алфавита . Приписывание слова к слову называется конкатенацией. Полученное при этом слово обозначается : .

Операция конкатенации обладает следующими свойствами:

а) ассоциативность: ;

б) существование нейтрального элемента: .

Очевидно, что эта операция некоммутативна.

Пусть и – два алфавита, и – соответствующие им множества слов. Отображение

называется словарным оператором.

Рассмотрим примеры словарных операторов для двоичных алфавитов .

Пример 1. Оператор сопоставляет каждому слову его первую букву:

.

Пример 2. Оператор производит в слове-аргументе замену каждого нуля на единицу и каждой единицы на нуль:

.

Пример 3. Оператор переписывает каждое слово слева направо:

.

Пример 4. Оператор определяется следующим образом:

,

где

,

,

…

.