1679
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Свободным моноидом''' (англ. ''free monoid'') <tex> M </tex> '''над множеством ''' <tex> S </tex> <tex>(</tex>обозначается как <tex> M_S )</tex> называется моноид над множеством <tex> S^* </tex> {{---}} набором всевозможных последовательностей (или списков) конечной длины (в том числе и нулевой), образованных из элементов множества <tex> S </tex> {{---}} с ассоциативной операцией <tex>\circ</tex> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#defconcat|конкатенации]] этих последовательностей.
}}
* <tex> S = \{1\} </tex>. Тогда <tex>S^* = \{[], [1], [1, 1], ... \} </tex>. Такой моноид с введённой на нём операцией сложения как объединением списков, [[Изоморфизм групп | изоморфен]] моноиду натуральных чисел.
Введём дополнительное определение, чтобы привести пример моноида, не являющегося свободным.
{{Определение
|definition=
'''Моноидом с порождающими отношениями''' (англ. ''equational presentation of monoid'') называется моноид, на котором введены дополнительные правила(то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида.
}}
Примером такого моноида является множество <tex> G </tex> всевозможных строк над алфавитом <tex> \Sigma = \{a, b\} </tex>, <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex>, что обозначает равенство строк <tex> ab </tex> и <tex> ba </tex> в моноиде. И хотя такой моноид образован всевозможными последовательностями, он не является свободным. Покажем это.
