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

и вообще

для всех i 0.

Последнее равенство показывает, что для всех i является собственным началом слова =24 src="images/referats/11735/image125.png">. Следовательно, - слово может быть определено как “ предел ” последовательности , i=0,1,2, … . Точнее, представляет собой - слово, начало которого, имеющее длину , есть , i=0,1,2, … .

3) Определение. Слово или - слово называется бесквадратным (бескубным), если оно не содержит подслова вида хх (соответственно х), где х – непустое слово.

Слово или - слово называется сильно бескубным, если если оно не содержит слов вида хха, где х – непустое слово, а а – первая буква слова х.

4) Может случиться, что слово w содержит два “перекрывающихся” вхождения х, т.е. подслово xy = zx, где . Если это не имеет место, то будем называть w словом без перекрытий.

II. Сформулируем основные теоремы.

Рассмотрим следующую DOL – систему G = ({a, b}, h, a), где h определяется следующим образом: h(a) =ab, h(b) = ba. Тогда последовательность S(G) начинается словами:

a, ab, abba, 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.

Теперь подведём итог полному решению проблемы Туэ в следующих теоремах:

1) “Если А состоит не менее чем из трёх символов, то над А существует бесквадратное - слово ”;

2) “Если А имеем не менее двух символов, то А существует сильно бескубное, а значит и бескубное - слово”.

III.Сейчас рассмотрим некоторые методы доказательства.

В формулировках основных теорем показано, как строятся - слова .

Теорема 3.1.

Слово и - слово свободно от перекрытий тогда и только тогда, когда оно является сильно бескубным.

Доказательство. Пусть w не свободно от перекрытий. Тогда w найдется подслово xy = zx, такое, что имеет место . Пусть а – первая буква слова z. По нашему предположению, x = zx, где первой буквой слова xтакже будет а. Следовательно, zza – подслово w и w не является сильно бескубеым.

Наоборот, предположим, что w не является сильно бескубным. Тогда в w найдётся слово zza, где а – первая буква z. Пологая z=аzмы видим, что х = а zа, y = zа, z = а z. Тогда xy = zx – подслово w, и, кроме того, выполняется . Отсюда следует, что w не свободно от перекрытий. Ч.т.д.

Теорема 3.2.

Ни одно слово, имеющее длину более 3, над алфавитом А из двух букв не является бесквадратным. Следовательно, над алфавиотм А не существует бесквадратных - слов.

Доказательство. Пусть А состоит из букв a и b. Существуют только 2 бесквадратных слова

аbа и bаb, (*)

так как все другие слова указанной длины:

содержит в качестве подслова либо , либо . С другой стороны, каким бы способом ни была приписана буква к любому слову из (*), результирующее слово в каждом случае будет содержать в качестве подслова одно из слов , , и, следовательно, не будет бесквадратным.Ч.т.д.

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