Изменения

Тройка Кортеж <tex>\langle G,\cdot: G \times G \to G, \varepsilon \in G \rangle</tex> называется [[моноид|моноидом]], если она он удовлетворяет следующим аксиомам:* Операция Бинарная операция <tex> \cdot \colon G \times G \rightarrow G </tex> — определена везде и [[Ассоциативная операция | ''ассоциативна'']].* Существует нейтральный элемент <tex> \varepsilon </tex> называется нейтральным элементом относительно <tex>\in G cdot</tex> относительно бинарной операции такой, чтото есть для него выполняется:: <tex> \forall x\in G : \varepsilon\cdot x=x \cdot \varepsilon = x</tex>. Иногда его обозначают <tex> \varepsilon_G </tex>, или <tex>e_G </tex>.

Другими словами, моноид {{---}} это [[Полугруппа|полугруппа]], в которую добавлен нейтральный элемент. Например,  == Примеры == * множество натуральных чисел <tex> \mathbb{N} </tex> с операцией сложения не является моноидом<tex>\langle \mathbb{N}, +, 0 \rangle</tex>* множество положительных целых <tex> \mathbb{Z}_+ </tex> с операцией умножения является моноидом <tex>\langle\mathbb{Z}_+, \cdot, а 1 \rangle</tex>* множество натуральных числел с операцией умножения является моноидом <tex>\langle \mathbb{N}, \cdot, 1 \rangle</tex> с нейтральным элементом <tex>1</tex> (наличие нуля не мешает этой структуре быть моноидом: <tex>1 \cdot 0 = 0</tex>, как того и требует аксиома нейтрального элемента), но тройка <tex>\langle \mathbb{N}, \cdot, 0 \rangle</tex> моноидом уже не является. == Свойства ==

'''Свободным моноидом''' (англ. ''free monoid'') <tex> M </tex> '''над множеством ''' <tex> S </tex> <tex>(</tex>обозначается как <tex> M_S )</tex> называется моноид над множеством <tex> S^* </tex> {{---}} набором всевозможных последовательностей (или списков) конечной длины (в том числе и нулевой), образованных из элементовмножества <tex> S </tex> {{---}} с ассоциативной операцией [[Основные определения: алфавит, слово, язык, конкатенация, полученных конечным числом применений ассоциативной свободный моноид слов; операции к элементам исходного множестванад языками#defconcat|конкатенации]] <tex>\texttt{++}</tex> этих последовательностей.

Тривиальный пример образуют множество <tex> S = \= Свободный моноид == {{\varnothing\} Определение|definition=Моноид </tex> и операция <tex> \cup M</tex>называется '''свободным''', если он [[Изоморфизм групп | изоморфен]] некоторому свободному моноиду над каким-то множеством. Тогда <tex> S^* \equiv \{\varnothing\}} </tex>.=== Примеры свободного моноида ===

Другой пример: * <tex> S = \langle \mathbb{N}, +, 0, 1\} rangle </tex>, операция {{---}} сложение. Тогда пример свободного моноида, так как он изоморфен свободному моноиду над <tex>S^* = \equiv {1\mathbb{N} </tex>: ** <tex>i(0) = []</tex>** <tex>i(a + b) = i(a) ~ \cup \texttt{0\++} ~ i(b)</tex>.

'''Свободным моноидомМоноидом с порождающими соотношениями''' (англ. ''equational presentation of monoid'' над множеством <tex> S </tex> ) называется моноид <tex> M </tex> вместе с отображением <tex> i\colon S \rightarrow M </tex> при условии, что для любого на котором введены дополнительные правила (то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида <tex> N </tex> и для любых отображений <tex> f \colon S \rightarrow N </tex> существует единственный [[Гомоморфизм групп | гомоморфизм]] моноидов <tex> \overline{f} \colon M_S \rightarrow N </tex> такой, что <tex> \overline{f} \circ i = f </tex>.

Примером такого моноида является множество <tex> G </tex> всевозможных строк над алфавитом <tex> \Sigma = \{a, b\} </tex>, <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex>, что обозначает равенство строк <tex> ab </tex> и <tex> ba </tex> в моноиде. И хотя такой моноид образован всевозможными последовательностями, он не является свободным. Покажем это. {{Теорема |statement= Моноид <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex> не является свободным|proof=Для начала покажем, что каждый элемент такого моноида можно представить в виде <tex> a^i b^j, i \geqslant 0, j \geqslant 0 </tex>. Докажем это конструктивно. Возьмём произвольную строку и будем в ней заменять все подстроки вида <tex> ba </tex> на подстроки <tex> ab </tex>. Если таких подстрок нет, то наша строка имеет вид <tex> a^i b^j </tex>, а если есть, то строка за конечное число шагов приведётся к указанному виду. '''Замечание''': конкатенация двух последовательностей <tex> a^i b^j </tex> и <tex> a^k b^t </tex> аналогична операции конкатенации строк, только после её применения строку надо привести к виду <tex> a^{i + k} b^{j + t} </tex>, поэтому результат операции равен не конкретной строке, а целому [[Отношение эквивалентности#Классы эквивалентности | классу эквивалентности]]. Предположим, что данный моноид свободный. Это наглядно показано следующей картинкойзначит, что он изоморфен какому-то свободному моноиду над множеством <tex> M_S </tex>, то есть существует биективное отображение <tex> f \colon G \to M_S </tex>. Оно сохраняет ассоциативность операций, поэтому  <tex> f(ab) = f(a) ~\texttt{++}~ f(b) </tex> <tex> f(ba) = f(b) ~\texttt{++}~ f(a) </tex> Следовательно, так как <tex> ab = ba </tex> и отображение <tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) ~\texttt{++}~ f(b) = f(b) ~\texttt{++}~ f(a) = f(ba) </tex>. Пусть <tex> |f(a)| = m, |f(b)| = n </tex>. Равенство этих последовательностей означает, что у последовательности <tex> f(a) ~\texttt{++}~ f(b) </tex> есть два [[Период и бордер, их связь | бордера]] длин <tex> m </tex> и <tex> n </tex> соответственно, значит, она периодическая и имеет период равный <tex>\gcd(n, m)</tex>. [[File:FreeMonoidConcatExample.png|300px]] Из этого следует, что последовательности <tex> f(a) </tex> и <tex> f(b) </tex> можно представить в виде конечного объединения некоторой подпоследовательности <tex> s </tex>, являющейся периодом и имеющей длину <tex>\gcd(n, m)</tex>. <tex> f(a) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{p} </tex> <tex> f(b) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ...~\texttt{++}~ s}^{q} , s \in M_S </tex>

== Ссылки Источники информации ==* [[wikipedia:Monoid | Wikipedia {{---}} Monoid ]]* [[wikipedia:ru:Моноид | Википедия {{---}} Моноид ]]