Свободные полугруппы
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
ba, abba baab, abba baab baab abba, … .
Теперь есть - слово, порожденное DOL системой G.
- слово является сильно бескубным.
Сформулируем следующее:
Существует бесквадратное - слово над алфавитом из четырех символов и cуществует бесквадратное - слово над алфавитом из трёх символов .
= где для всех j1.
Введём новые обозначения для элементов А1, положив
[aa] = 1, [ab] = 2, [ba] = 3, [bb] = 4.
Теперь начало имеет вид
2432312431232432312324312432312…
Рассмотрим алфавит А2 = {1, 2, 3}. Определим - слово кА результат замены в всех вхождений символа 4 символом 1.
Теперь подведём итог полному решению проблемы Туэ в следующих теоремах:
- “Если А состоит не менее чем из трёх символов, то над А существует бесквадратное
- слово ”;
- “Если А имеем не менее двух символов, то А существует сильно бескубное, а значит и бескубное
- слово”.
III.Сейчас рассмотрим некоторые методы доказательства.
В формулировках основных теорем показано, как строятся - слова .
Теорема 3.1.
Слово и - слово свободно от перекрытий тогда и только тогда, когда оно является сильно бескубным.
Доказательство. Пусть w не свободно от перекрытий. Тогда w найдется подслово xy = zx, такое, что имеет место . Пусть а первая буква слова z. По нашему предположению, x = zx , где первой буквой слова x также будет а. Следовательно, zza подслово w и w не является сильно бескубеым.
Наоборот, предположим, что w не является сильно бескубным. Тогда в w найдётся слово z za, где а первая буква z. Пологая z=аz мы видим, что х = а zа, y = zа, z = а z. Тогда xy = zx подслово w, и, кроме того, выполняется . Отсюда следует, что w не свободно от перекрытий. Ч.т.д.
Теорема 3.2.
Ни одно слово, имеющее длину более 3, над алфавитом А из двух букв не является бесквадратным. Следовательно, над алфавиотм А не существует бесквадратных - слов.
Доказательство. Пусть А состоит из букв a и b. Существуют только 2 бесквадратных слова
аbа и bаb, (*)
так как все другие слова указанной длины:
содержит в качестве подслова либо , либо . С другой стороны, каким бы способом ни была приписана буква к любому слову из (*), результирующее слово в каждом случае будет содержать в качестве подслова одно из слов , , и, следовательно, не будет бесквадратным.Ч.т.д.
Теоремя 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) не есть или .Ч.т.д.
Литература
- Курош А.Т. Лекции по общей алгебре. М.: Наука, 1973.
- Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985.
- Саломаа А. Жемчужины теории формальных языков. М.: Мир, 1986.
- Скорняков Л.А. Элементы алгебры. М.: Наука, 1986.