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

Определение

Определим последовательность строк [math]T_n[/math] над двухбуквенным алфавитом [math]\{a, b\}[/math] следующим образом: [math]T_n = t_0 t_1 \dots t_{2^n-1}[/math], где:

• [math]t_i = a[/math], если двоичная запись числа [math]i[/math] содержит чётное число единиц
• [math]t_i = b[/math] иначе

Строки этой последовательности называются строками Туэ-Морса.

Примеры

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

• [math]T_0 = a[/math]
• [math]T_1 = ab[/math]
• [math]T_2 = abba[/math]
• [math]T_3 = abbabaab[/math]
• [math]T_4 = abbabaabbaababba[/math]

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

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

Заметим, что соответсвующие индексы символов при приписывании суффикса к строке [math]T_n[/math] получаются добавлением к индексам [math]i = 0, 1, \dots, 2^n - 1[/math] числа [math]2^n[/math]. Количество единиц в двоичной записи числа [math]i + 2^n[/math] ровно на один больше, чем в двоичной записи числа [math]i[/math]. Поэтому приписываемый суффикс есть ни что иное, как исходная строка с инвертированными символами.

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

Ссылки

• Wikipedia — Thue-Morse sequence
• Wolfram Mathworld — Thue-Morse sequence