Слово Туэ-Морса — различия между версиями

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

Версия 16:43, 21 июня 2012

Определение:
Определим последовательность строк [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]\varphi[/math] — морфизм, инвертирующий символы:

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

тогда для строк Туэ-Морса верно следующее соотношение: [math]T_{n + 1} = T_n \varphi(T_n)[/math]
Доказательство:
[math]\triangleright[/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 \lt 2^n[/math]) ровно на один больше, чем в двоичной записи числа [math]i[/math]. Поэтому приписываемая строка есть ни что иное, как исходная строка с инвертированными символами.
[math]\triangleleft[/math]

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

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

См. также

Слово Фибоначчи

Ссылки