3622
правки
Изменения
добавлена теорема о несвободном моноиде
Для начала покажем, что каждый элемент такого моноида можно представить в виде <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 : G \to M_S </tex>. Это Оно сохраняет ассоциативность операций, поэтому <tex> f(ab) = f(a) \cdot f(b) </tex> <tex> f(ba) = f(b) \cdot f(a) </tex> Следовательно, так как <tex> ab = ba </tex> и отображение<tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) \cdot f(b) = f(b) \cdot f(a) = f(ba) </tex>. Равенство этих последовательностей означает, что у строки <tex> f(a) \cdot f(b) </tex> есть [[Период и бордер, их связь | бордер]], а значит, она периодическая. TODO: картинка, которая объяснит все равенства Из этого следует, что <tex> f(a) = \overbrace{s \cdot s \cdot ... \cdot s}^{p} </tex> <tex> f(b) = \overbrace{s \cdot s \cdot ... \cdot s}^{q} , s \in M_S </tex> Пусть НОК<tex>(p, q) = l</tex>, тогда <tex dpi = 140> \overbrace{f(a) \cdot f(a) \cdot ... \cdot f(a)}^{\frac{l}{p}} = \overbrace{s \cdot s \cdot ... \cdot s}^{l} </tex> <tex dpi = 140> \overbrace{f(b) \cdot f(b) \cdot ... \cdot f(b)}^{\frac{l}{q}} = \overbrace{s \cdot s \cdot ... \cdot s}^{l} </tex> Откуда следует, что <tex dpi = 140> a^{\frac{l}{p}} = b^{\frac{l}{q}} </tex>, то есть отображение <tex> f </tex> не является изоморфизмом. Значит, мы пришли к противоречию, предположив, что данный моноид <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex> является свободным.
}}
