Обзор результатов по проблеме Туэ

 

Аксель Туэ (1863 – 1922) – норвежский математик. Хотя он был специалистом по теории чисел, но остался в истории, как родоначальник теории формальных языков, связанные с решёнными им задачами о формальных словах известных теперь, как проблемы Туэ. Задачи решены в 1912 – 1914г.

I. Введём следующие определения.

1) Сформулируем определение  - слова:

Бесконечная последовательность элементов алфавита А называется  - словом или сверхсловом. Таким образом,  - слово может быть отождествлено с отображением множества целых чисел в А. Очень удобным средством задания конкретных  - слов являются DOL – системы.

    2) Тройка G = (A, h, w), A – алфавит,  - морфизм и w – слово над А, называется DOL – системой. DOL – система G определяет S(G) слов над А:

                    .

Рассмотрим DOL – систему G = (A, h, w), такую, что , х Z(A), т.е. w – собственное начало слова h(w) и, кроме того, h является нестирающим (т.е. h(a)=  для всех а из А). Тогда

      и вообще

           для всех i  0.

Последнее равенство показывает, что  для всех i является собственным началом слова . Следовательно,  - слово  может быть определено как “ предел ” последовательности , 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уществует бесквадратное  - слово  над алфавитом из трёх символов  .

   

                   =  где для всех j 1.

Введём новые обозначения для элементов А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 найдётся слово z  z a, где а – первая буква 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) не есть  или .Ч.т.д.

  Литература

 

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

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

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

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