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

над алфавитом А - полугруппа, элементами к-рой. являются всевозможные конечные последовательности элементов из А(букв), а операция состоит в приписывании одной последовательности к другой. Элементы С. п. принято называть словами, а операцию часто называют конкатенацией. Ради удобства нередко рассматривают также и пустое слово 1 (длина к-рого по определению равна нулю), полагая w1=1w=w для любого слова w;возникающая таким образом полугруппа с единицей наз. с в о б о д н ы м м о н о и д о м над А. С. п. (свободный моноид) над Ачасто обозначают А + (соответственно А*). Для С. п. А + алфавит Аявляется единственным неприводимым порождающим множеством; он состоит в точности из элементов, неразложимых в произведение. Буквы из Аназ. свободными образующими. С. п. определяется однозначно с точностью до изоморфизма мощностью своего алфавита; эта мощность наз. рангом свободной полугруппы. С. п. ранга 2 имеет подполугруппы, являющиеся С. п. счетного ранга. С. п. являются свободными алгебрами в классе всех полугрупп. Следующие условия для полугруппы Fэквивалентны: 1) Fесть С. п.; 2) Fимеет порождающее множество Атакое, что любой элемент из Fединственным образом представим в виде произведения элементов из А;3) Fудовлетворяет закону сокращения, не содержит идемпотентов, каждый элемент из Fимеет конечное число делителей, и для любых [img: http://localhost:8080/file/041902-60.jpg] равенство [img: http://localhost:8080/file/041902-61.jpg] влечет, что и=и' или один из элементов и, и' есть левый делитель другого. Всякая подполугруппа Нв С. п. имеет единственное неприводимое порождающее множество, состоящее из элементов, неразложимых в H в произведение; однако не всякая подполугруппа С. п. сама свободна. Следующие условия для подполугруппы Нв С. п. Fэквивалентны: 1) Несть С. п.; 2) для любого [img: http://localhost:8080/file/041902-62.jpg] из того, что [img: http://localhost:8080/file/041902-63.jpg] и [img: http://localhost:8080/file/041902-64.jpg], следует, что [img: http://localhost:8080/file/041902-65.jpg]; 3) для любого [img: http://localhost:8080/file/041902-66.jpg] из того, что [img: http://localhost:8080/file/041902-67.jpg], следует, что [img: http://localhost:8080/file/041902-68.jpg]. Для произвольных различных слов и, v в С. п. Fлибо ии v являются свободными образующими порожденной ими подполугруппы, либо существует [img: http://localhost:8080/file/041902-69.jpg] такое, что [img: http://localhost:8080/file/041902-70.jpg] для нек-рых натуральных k, l;вторая альтернатива выполняется тогда и только тогда, когда иv=vu. Всякая подполугруппа с тремя образующими в С. п. будет конечно определенной полугруппой, но существуют подполугруппы с четырьмя образующими, не являющиеся конечно определенными. С. п. естественно возникают в автоматов алгебраической теории (см. также [5], [6]), теории кодирования (см. Кодирование алфавитное,[4] - [6]), теории формальных языков и формальных грамматик (см. [3], [5], [6]). С указанными областями связана проблематика решения уравнений в С. п. (см. [7] - [9]). Существует алгоритм, распознающий разрешимость произвольных уравнений в С. п.