Свободные полугруппы

Теоремя 3.3.

Ни , ни не входят в качестве подслова в . Ни ababa, ни babab не входят в качестве подслова в . Следовательно, лю

бое подслово х - слова , такое, что , содержит в качестве подслова либо , либо .

Доказательство. Докажем первое утверждение. Если слово или входит в качестве подслова в , то оно входит в качестве подслова в некоторое w. Но это не возможно, так как w= h(w) и, следовательно, wполучено приписыванием слов ab и ba в некотором порядке.

Докажем второе утверждение. Предположим, что ababa входит в качестве подслова в - слова , начиная с j-й его буквы. Тогда используя = …, запишем

= ababa. (**)

Выберем настолько большое j что . Тогда вхождения (**) целиком лежит в w.Ещё раз используя соотношение w= h(w), заключаем, что в wв качестве подслова входит либо , либо в зависимости от того, является ли j в (**) нечетным или четным. Но это не возможно в силу доказанного выше первого утверждения. Аналогично и для babab не входит в .

Наконец, последнее утверждение является следствием второго, так как, за исключением слов ababa и babab, любое слово длины 5 над {a,b} содержит в качестве подслова либо , либо . Ч.т.д.

Теорема 3.4.

Предположим, что или входит в качестве подслова в , начиная с j-й; тогда j четно.

Доказательство. Используя обозначения предыдущей теоремы, предположим, что есть или . Вновь выбираем такое i, что , и применяем соотношение w= h(w). В силу этого соотношения, если j нечетно, то есть либо h(a), либо h(b). Так как ни h(a), ни h(b) не есть или .Ч.т.д.

Литература

1. Курош А.Т. Лекции по общей алгебре. – М.: Наука, 1973.

2. Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир, 1985.

3. Саломаа А. Жемчужины теории формальных языков. – М.: Мир, 1986.

4. Скорняков Л.А. Элементы алгебры. – М.: Наука, 1986.

 Скачать реферат