Слово Туэ-Морса

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Определим последовательность строк T_n над двухбуквенным алфавитом \{a, b\} следующим образом: T_n = t_0 t_1 \dots t_{2^n-1}, где:
  • t_i = a, если двоичная запись числа i содержит чётное число единиц
  • t_i = b, иначе.
Строки этой последовательности называются строками Туэ-Морса (англ. Thue–Morse sequence).


Содержание

[править] Примеры

Приведём первые пять строк Туэ-Морса:

  • T_0 = a
  • T_1 = ab
  • T_2 = abba
  • T_3 = abbabaab
  • T_4 = abbabaabbaababba

[править] Свойства и эквивалентные определения

[править] Свойство о получении следующей строки

Как видно из определения, символ на i-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей строке некоторой другой строки.

Теорема:
Пусть \varphi — морфизм, инвертирующий символы:

\varphi(x) = \left\{ \begin{array}{rl}  b, & x = a \\ a, & x = b, \\ \end{array} \right.

тогда для строк Туэ-Морса верно следующее соотношение: T_{n + 1} = T_n \varphi(T_n)
Доказательство:
\triangleright
Заметим, что соответствующие индексы символов при приписывании новой строки к строке T_n получаются добавлением к индексам i = 0, 1, \dots, 2^n - 1 числа 2^n. Количество единиц в двоичной записи числа i + 2^n (i < 2^n) ровно на один больше, чем в двоичной записи числа i. Поэтому приписываемая строка есть ни что иное, как исходная строка с инвертированными символами.
\triangleleft

Данная теорема позволяет определять последовательность строк Туэ-Морса следующим образом: T_0 = a, T_{n + 1} = T_n \varphi(T_n).

Часто рассматривают предельный случай — бесконечную строку Туэ-Морса, любой символ которой можно получить из обычной строки Туэ-Морса с достаточно большим номером. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений.

[править] Свойство о подстроках

Теорема:
Не существует двух равных как строки подстрок строки T_n, имеющих пересекающиеся вхождения в T_n
Доказательство:
\triangleright

Заметим, что t_{2n}=t_n для n \geqslant 0, так как количество единиц числа 2n и n одинаково. Так же заметим, что t_{2n+1}=\varphi(t_n) для n \geqslant 0, потому что 2n и 2n+1 одинаковы в двоичной системе, кроме последнего бита, а количество единиц числа 2n и n одинаково.

Пусть существует две равные как строки подстрок строки T_n, имеющих пересекающиеся вхождения в T_n, тогда T_n=ucxcxcv, где u,c,x,v — подстроки строки T_n, а строка cxc — искомая подстрока.

Пусть m=|cx| и k=|u|, тогда t_{k+j}=t_{k+j+m} по предположению при 0 \leqslant j \leqslant m.

Рассмотрим наименьшее m\geqslant 1. Тогда возможны два случая: m четно и нечетно:

  1. m четно.
    Тогда пусть m=2m'. Рассмотрю два случая: k четно или нечетно:
    • k четно:
      Пусть k=2k'. Так как t_{k+j}=t_{k+j+m} при 0 \leqslant j \leqslant m, тогда очевидно, что t_{2k'+2j'}=t_{2k'+2j'+2m'} для 0 \leqslant j' \leqslant m'. Так как t_{2k'+2j'}=t_{k'+j'} и t_{2k'+2j'+2m'}=t_{k'+j'+m'} очевидно, что t_{k'+j'}=t_{k'+j'+m'} для 0 \leqslant j' \leqslant m'. Это противоречие, так как m минимально.
    • k нечетно:
      Пусть k=2k'+1. Тогда, как и в предыдущем случае t_{2k'+2j'+1}=t_{2k'+2j'+2m'+1} для 0 \leqslant j' \leqslant m' и тогда t_{k'+j'}=t_{k'+j'+m'} для 0 \leqslant j' \leqslant m', что является опять противоречием из-за минимальности m
  2. m нечетно.
    Тогда рассмотрю три случая: m \geqslant 5, m=3 и m=1. Пусть b_n=\left\{ \begin{array}{rl}  a, & t_n=t_{n-1} \\ b, & t_n \ne t_{n-1} \\ \end{array} \right., для n \geqslant 1. Заметим, что b_{4n+2}=a так как 4n+2 и 4n+1 одинаково записываются в двоичной записи, кроме последних двух битов, которые равны 10 и 01 соответственно и значит t_{4n+2}=t_{4n+1}. Так же заметим, что b_{2n+1}=b, так как 2n+1 и 2n одинаково записываются в двоичной системе, кроме последнего бита и значит, что t_{2n+1}=\varphi(t_{2n})
    • m нечетно и m \geqslant 5.
      Тогда b_{k+j}=b_{k+j+m} для 1 \leqslant j \leqslant m. С m \geqslant 5 существует j, такое что k+j=2 по модулю 4. Тогда для k+j точно известно, что b_{k+j}=0, но с другой стороны k+j+m — нечетно, значит b_{k+j+m}=1. Противоречие.
    • m=3.
      Аналогично: b_{k+j}=b_{k+j+3} для 1 \leqslant j \leqslant 3. Найдем j, чтобы k+j=2 или k+j=3 по модулю 4. Если k+j=2 по модулю 4, то противоречие получается так же, как в предыдущем пункте. Рассмотрим k+j=3 по модулю 4, тогда b_{k+j}=1, но b_{k+j+3}=0. Это опять противоречие.
    • m=1.
      Тогда t_k=t_{k+1}=t_{k+2} из чего следует, что t_{2n}=t_{2n+1} для n=\dfrac{k}{2}, но t_{2n}=\varphi(t_{2n+1}) \ne t_{2n+1}. Противоречие.
\triangleleft

[править] См. также

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты