3622
правки
Изменения
картинка, дописана теорема
{{Определение
|definition=
'''Свободным моноидом''' (англ. ''free monoid'') <tex> M </tex> '''над множеством''' <tex> S </tex> <tex>(</tex>обозначается как <tex> M_S )</tex> называется моноид над множеством <tex> S^* </tex> {{---}} набором всевозможных последовательностей (или списков) конечной длины (в том числе и нулевой), образованных из элементов множества <tex> S </tex> {{---}} с ассоциативной операцией <tex>\texttt{++}</tex> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#defconcat|конкатенации]] <tex>\texttt{++}</tex> этих последовательностей.
}}
* тривиальный пример: множество <tex> S = \varnothing </tex>. Тогда <tex> S^* = \{\varnothing\} </tex>.
* <tex> S = \{1\} </tex>. Тогда <tex>S^* = \{[], [1], [1, 1], ... \} </tex>. Такой моноид с введённой на нём операцией сложения как объединением списков, [[Изоморфизм групп | изоморфен]] моноиду натуральных чисел.
{{Определение
|definition=
Моноид <tex>M</tex> называется '''свободным''', если он [[Изоморфизм групп | изоморфен ]] некоторому свободному моноиду над каким-то множеством.
}}
* <tex>\langle \mathbb{N}, +, 0 \rangle </tex> {{---}} пример свободного моноида, так как он изоморфен свободному моноиду над <tex>S = \{1\}</tex>:
** <tex>i(0) = []</tex>
** <tex>i(a + b) = i(a) ~ \texttt{++} ~ i(b)</tex>
Для начала покажем, что каждый элемент такого моноида можно представить в виде <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> ba </tex> на <tex> ab </tex> можно рассматривать, как уменьшения числа инверсий в последовательности, а их точно конечное число, так как все последовательности имеют конечную длину.
Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду над множество <tex> M_S </tex>, то есть существует биективное отображение <tex> f \colon G \to M_S </tex>. Оно сохраняет ассоциативность операций, поэтому <tex> f(ab) = f(a) ~\cdot texttt{++}~ f(b) </tex>
<tex> f(ba) = f(b) ~\cdot texttt{++}~ f(a) </tex>
Следовательно, так как <tex> ab = ba </tex> и отображение <tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) ~\cdot texttt{++}~ f(b) = f(b) ~\cdot texttt{++}~ f(a) = f(ba) </tex>. Пусть <tex> |f(a)| = m, |f(b)| = n </tex>. Равенство этих последовательностей означает, что у строки последовательности <tex> f(a) ~\cdot texttt{++}~ f(b) </tex> есть два [[Период и бордер, их связь | бордербордера]]длин <tex> m </tex> и <tex> n </tex> соответственно, а значит, она периодическаяи имеет период равный НОД<tex>(n, m)</tex>.
Из этого следует, чтопоследовательности <tex> f(a) </tex> и <tex> f(b) </tex> можно представить в виде конечного объединения некоторой подпоследовательности <tex> s </tex>, являющейся периодом и имеющей длину НОД<tex>(n, m)</tex>.
<tex> f(a) = \overbrace{s ~\cdot texttt{++}~ s ~\cdot texttt{++}~ ... ~\cdot texttt{++}~ s}^{p} </tex>
<tex> f(b) = \overbrace{s ~\cdot texttt{++}~ s ~\cdot texttt{++}~ ... ~\cdot texttt{++}~ s}^{q} , s \in M_S </tex>
Пусть НОК<tex>(p, q) = l</tex>, тогда
<tex dpi = 140> \overbrace{f(a) ~\cdot texttt{++}~ f(a) ~\cdot texttt{++}~ ... ~\cdot texttt{++}~ f(a)}^{l / p} = \overbrace{s ~\fractexttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l}</tex> <tex dpi> \overbrace{f(b) ~\texttt{++}~ f(b) ~\texttt{++}~ ... ~\texttt{p++}~ f(b)}^{l / q} = \overbrace{s ~\cdot texttt{++}~ s ~\cdot texttt{++}~ ... ~\cdot texttt{++}~ s}^{l} </tex>
Откуда следует, что <tex dpi = 140> \overbracea^{f(b) \cdot f(l / p} = b) \cdot ... \cdot f(b)}^{\frac{l}{/ q}} </tex>, то есть отображение <tex> f </tex> не является изоморфизмом. Значит, мы пришли к противоречию, предположив, что данный моноид <tex dpi = 130> G = \overbraceSigma^{s \cdot s \cdot ... \cdot s*}^_{l/ab = ba} </tex> является свободным.
}}
