Введение

В абстрактной алгебре свободный моноид на множестве — это моноид, элементы которого представляют собой все конечные последовательности (или строки) из нуля или более элементов этого множества, с конкатенацией строк в качестве моноидной операции и с единственной последовательностью, состоящей из нуля элементов, часто называемой пустой строкой и обозначаемой ε или λ, в качестве нейтрального элемента. Свободный моноид на множестве A обычно обозначается A*. Свободная полугруппа на A — это подполугруппа A*, содержащая все элементы, кроме пустой строки. Обычно обозначается A+. В более общем случае, абстрактный моноид (или полугруппа) S называется свободным, если он изоморфен свободному моноиду (или полугруппе) на некотором множестве. Как следует из названия, свободные моноиды и полугруппы — это объекты, удовлетворяющие обычному универсальному свойству, определяющему свободные объекты в соответствующих категориях моноидов и полугрупп. Отсюда следует, что любой моноид (или полугруппа) является гомоморфным образом свободного моноида (или полугруппы). Изучение полугрупп как образов свободных полугрупп называется комбинаторной теорией полугрупп. Свободные моноиды (и моноиды в целом) ассоциативны по определению; то есть они записываются без скобок, указывающих группировку или порядок операций. Неассоциативным аналогом является свободная магма.

Сочетание слов

Мы определяем пару слов в A* вида uv и vu как сопряжённые: сопряжёнными к слову, таким образом, являются его циклические сдвиги. Два слова являются сопряжёнными в этом смысле, если они сопряжены в смысле теории групп как элементы свободной группы, порождённой A.

Равнодельность

Свободный моноид равноразделим: если уравнение mn = pq выполняется, то существует s, такое, что либо m = ps, sn = q (пример см. изображение), либо ms = p, n = sq. Этот результат также известен как лемма Леви. Моноид свободен тогда и только тогда, когда он градуирован (в строгом смысле, что только тождественный элемент имеет градуировку 0) и равноразделим. Субмоноид A стабилен тогда и только тогда, когда он свободен. Например, используя множество битов { "0", "1" } в качестве A, множество N всех битовых строк, содержащих четное число "1", является стабильным субмоноидом, поскольку если u содержит четное число "1", и ux также, то x также должно содержать четное число "1". Хотя N не может быть свободно сгенерирован любым набором отдельных битов, он может быть свободно сгенерирован набором битовых строк { "0", "11", "101", "1001", "10001", } – набором строк вида "10ⁿ1" для некоторого неотрицательного целого числа n (вместе со строкой "0").

Коды

Набор свободных генераторов для свободного моноида P называется базисом для P: множество слов C является кодом, если C* является свободным моноидом, а C – базисом. Подмоноид N моноида A* называется правоунитарным, если x и xy принадлежат N, то y принадлежит N. Подмоноид порождается префиксом тогда и только тогда, когда он правоунитарен.

Факторизация

Факторизация свободного моноида — это последовательность подмножеств слов, обладающая свойством, что любое слово в свободном моноиде может быть представлено как конкатенация элементов, взятых из этих подмножеств. Теорема Чена — Фокса — Линдона утверждает, что слова Линдона дают факторизацию. В более общем случае, слова Холла также обеспечивают факторизацию, при этом слова Линдона являются частным случаем слов Холла.

Морфизмы

Моноидный морфизм f из свободного моноида B* в моноид M — это отображение, такое что f(xy) = f(x)⋅f(y) для слов x, y и f(ε) = ι, где ε и ι обозначают единичные элементы B* и M соответственно. Морфизм f определяется своими значениями на буквах B, и наоборот, любое отображение из B в M расширяется до морфизма. Морфизм называется нестирающим (или непрерывным), если ни одна буква B не отображается в ι, и тривиальным, если каждая буква B отображается в ι. Морфизм f из свободного моноида B* в свободный моноид A* называется полным, если каждая буква A встречается хотя бы в одном слове из образа f; циклическим, если образ f содержится в {w}* для некоторого слова w из A*. Морфизм f называется k-равномерным, если длина |f(a)| постоянна и равна k для всех a из B. 1-равномерный морфизм строго алфавитен.

Морфизм f из свободного моноида B* в свободный моноид A* упростим, если существует алфавит C кардинальности меньше, чем у B, такой что морфизм f факторизуется через C*, то есть является композицией морфизма из B* в C* и морфизма из C* в A*; в противном случае f называется элементарным. Морфизм f называется кодом, если образ алфавита B при отображении f является кодом. Каждый элементарный морфизм является кодом.

Набор испытаний

Для L, являющегося подмножеством B*, конечное подмножество T из L является тестовым множеством для L, если морфизмы f и g на B* согласуются на L тогда и только тогда, когда они согласуются на T. Гипотеза Эренфюхта утверждает, что любое подмножество L имеет тестовое множество: это было независимо доказано Альбертом и Лоуренсом, Макнотоном и Губой. Доказательства опираются на теорему Гильберта об основаниях.

Эндоморфизмы

Эндоморфизм A* — это морфизм из A* в само себя. Тождественное отображение I является эндоморфизмом A*, а эндоморфизмы образуют моноид относительно композиции функций. Эндоморфизм f называется пролонгируемым, если существует буква a такая, что f(a) = as для некоторой непустой строки s.