Свободная Полугруппа

над алфавитом А - полугруппа, элементами к-рой. Являются всевозможные конечные последовательности элементов из А(букв), а операция состоит в приписывании одной последовательности к другой. Элементы С. П. Принято называть словами, а операцию часто называют конкатенацией. Ради удобства нередко рассматривают также и пустое слово 1 (длина к-рого по определению равна нулю), полагая w1=1w=w для любого слова w;возникающая таким образом полугруппа с единицей наз. С в о б о д н ы м м о н о и д о м над А. С . П . (свободный моноид) над Ачасто обозначают А + (соответственно А*). Для С. П. А + алфавит Аявляется единственным неприводимым порождающим множеством. Он состоит в точности из элементов, неразложимых в произведение. Буквы из Аназ.

Свободными образующими. С. П. Определяется однозначно с точностью до изоморфизма мощностью своего алфавита. Эта мощность наз. Рангом свободной полугруппы. С. П. Ранга 2 имеет подполугруппы, являющиеся С. П. Счетного ранга. С. П. Являются свободными алгебрами в классе всех полугрупп. Следующие условия для полугруппы Fэквивалентны. 1) Fесть С. П. 2) Fимеет порождающее множество Атакое, что любой элемент из Fединственным образом представим в виде произведения элементов из А;3) Fудовлетворяет закону сокращения, не содержит идемпотентов, каждый элемент из Fимеет конечное число делителей, и для любых равенство влечет, что и=и' или один из элементов и, и' есть левый делитель другого. Всякая подполугруппа Нв С. П. Имеет единственное неприводимое порождающее множество, состоящее из элементов, неразложимых в H в произведение.

Однако не всякая подполугруппа С. П. Сама свободна. Следующие условия для подполугруппы Нв С. П. Fэквивалентны. 1) Несть С. П. 2) для любого из того, что и , следует, что . 3) для любого из того, что , следует, что . Для произвольных различных слов и, v в С. П. Fлибо ии v являются свободными образующими порожденной ими подполугруппы, либо существует такое, что для нек-рых натуральных k, l;вторая альтернатива выполняется тогда и только тогда, когда иv=vu. Всякая подполугруппа с тремя образующими в С. П. Будет конечно определенной полугруппой, но существуют подполугруппы с четырьмя образующими, не являющиеся конечно определенными. С. П. Естественно возникают в автоматов алгебраической теории (см. Также [5], [6]), теории кодирования (см.

Кодирование алфавитное,[4] - [6]), теории формальных языков и формальных грамматик (см. [3], [5], [6]). С указанными областями связана проблематика решения уравнений в С. П. (см. [7] - [9]). Существует алгоритм, распознающий разрешимость произвольных уравнений в С. П. Лит.:[1] К л и ф ф о р д А., П р е с т о н Г., Алгебраическая теория полугрупп, пер. С англ., т. 1-2, М., 1972. [2] Л я п и н Е. С., Полугруппы, М., 1960. [3] Г р о с с М., Л а н т е н А., Теория формальных грамматик, пер. С франц., М., 1971. [4] М а р к о в А. А., Введение в теорию кодирования, М., 1982. [5] Е i 1 е n b е r g S., Аutоmаtа, lаnguages аnd mа-chines, v. А-В, N. Y.-L., 1974-76. [6] L а 1 1 е m е n t G., Semigroups аnd соmbinatoriа1 арplications, N. Y.- [а.

О.], 1979. [7] L е n t i n А., Еquations dans 1еs mоnoides libres, Р., 1972. [8] X м е л е в с к и й Ю. И., Уравнения в свободной полугруппе, М., 1971 (Тр. Матем. Ин-та АН СССР, т. 107). [9] М а к а н и н Г. С., "Матем. Сб.", 1977, т. 103, № 2, с. 147- 236. Л. Н. Шеврин..