Бесплатный моноид
В абстрактной алгебре свободный моноид в наборе — это моноид , элементами которого являются все конечные последовательности (или строки) из нуля или более элементов из этого набора, с конкатенацией строк в качестве операции моноида и с уникальной последовательностью нулевых элементов, часто называется пустой строкой и обозначается ε или λ как элемент идентичности . Свободный моноид на множестве A обычно обозначается A ∗ . Свободная полугруппа на A — это подполугруппа A ∗содержащий все элементы, кроме пустой строки. Обычно обозначается A + . [1] [2]
В более общем смысле абстрактный моноид (или полугруппа) S описывается как свободный , если он изоморфен свободному моноиду (или полугруппе) на некотором множестве. [3]
Как следует из названия, свободные моноиды и полугруппы — это те объекты, которые удовлетворяют обычному универсальному свойству , определяющему свободные объекты в соответствующих категориях моноидов и полугрупп. Отсюда следует, что каждый моноид (или полугруппа) возникает как гомоморфный образ свободного моноида (или полугруппы). Изучение полугрупп как образов свободных полугрупп называется комбинаторной теорией полугрупп.
Свободные моноиды (и моноиды вообще) ассоциативны по определению; то есть они написаны без каких-либо скобок, чтобы показать группировку или порядок работы. Неассоциативный эквивалент — свободная магма .
Моноид ( N 0 ,+) натуральных чисел (включая ноль) при сложении является свободным моноидом на одноэлементной свободной образующей, в данном случае на натуральном числе 1. Согласно формальному определению, этот моноид состоит из всех последовательностей типа «1 ", "1+1", "1+1+1", "1+1+1+1" и так далее, включая пустую последовательность. Отображение каждой такой последовательности на результат ее вычисления [4] , а пустой последовательности на ноль устанавливает изоморфизм множества таких последовательностей на N 0 . Этот изоморфизм совместим с «+», то есть для любых двух последовательностей s и t , если s отображается (т.е.к n , то их конкатенация s + t отображается в сумму m + n .
В теории формального языка обычно рассматривается конечное множество «символов» A (иногда называемое алфавитом). Конечная последовательность символов называется «словом над A », а свободный моноид A * называется « звездой Клини над A ». Таким образом, абстрактное изучение формальных языков можно рассматривать как изучение подмножеств конечно порожденных свободных моноидов.
