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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства и эквивалентные определения)
(Свойства и эквивалентные определения)
Строка 37: Строка 37:
  
 
Часто рассматривают предельный случай — бесконечную строку Туэ-Морса, любой символ которой можно получить из обычной строки Туэ-Морса с достаточно большим номером. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений.
 
Часто рассматривают предельный случай — бесконечную строку Туэ-Морса, любой символ которой можно получить из обычной строки Туэ-Морса с достаточно большим номером. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений.
 +
 +
{{Теорема
 +
|statement=
 +
Не существует двух равных как строки подстрок строки <tex>T_n</tex>, имеющих пересекающиеся вхождения в <tex>T_n</tex>
 +
|proof=
 +
Очевидно что <tex>t_{2n}=t_n</tex> и <tex>t_{2n+1}=\varphi(t_n)</tex> для <tex>n \ge 0</tex>
 +
Пусть существует две равные как строки подстрок строки <tex>T_n</tex>, имеющих пересекающиеся вхождения в <tex>T_n</tex>, тогда <tex>T_n=ucxcxcv</tex>, где <tex>u,c,x,v</tex> {{---}} подстроки строки <tex>T_n</tex>
 +
 +
Пусть <tex>m=|cx|</tex> и <tex>k=|u|</tex>, тогда <tex>t_{k+j}=t_{k+j+m}</tex> по предположению при <tex>0 \le j \le m</tex>.
 +
 +
Рассмотрим наименьшее <tex>m\ge 1</tex>. Тогда возможны два случая: <tex>m</tex> четно и нечетно:
 +
# <tex>m</tex> четно, тогда пусть <tex>m=2m'</tex>. Рассмотрю два случая: <tex>k</tex> четно или нечетно:
 +
#* <tex>k</tex> четно: Пусть <tex>k=2k'</tex>. Так как <tex>t_{k+j}=t_{k+j+m}</tex> при <tex>0 \le j \le m</tex>, тогда очевидно, что <tex>t_{2k'+2j'}=t_{2k'+2j'+2m'}</tex> для <tex> 0 \le j' \le m'</tex>. Так как <tex>t_{2k'+2j'}=t_{k'+j'}</tex> и <tex>t_{2k'+2j'+2m'}=t_{k'+j'+m'}</tex> очевидно, что <tex>t_{k'+j'}=t_{k'+j'+m'}</tex> для <tex>0 \le j' \le m'</tex>. Это противоречие, так как <tex>m</tex> минимально.
 +
#* <tex>k</tex> нечетно: Пусть <tex>k=2k'+1</tex>. Тогда, как и в предыдущем случае <tex>t_{2k'+2j'+1}=t_{2k'+2j'+2m'+1}</tex> для <tex>0 \le j' \le m'</tex> и тогда <tex>t_{k'+j'}=t_{k'+j'+m'}</tex> для <tex>0 \le j' \le m'</tex>, что является опять противоречием из-за минимальности <tex>m</tex>
 +
#<tex>m</tex> нечетно, тогда рассмотрю три случая: <tex>m \ge 5</tex>, <tex>m=3</tex> и <tex>m=1</tex>. Пусть <tex>b_n=\left\{ \begin{array}{rl}
 +
a, & t_n=t_{n-1} \\
 +
b, & t_n \ne t_{n-1}, \\
 +
\end{array} \right.</tex> для <tex>n \ge 1</tex>. Заметим, что <tex>b_{4n+2}=a</tex>  так как <tex>4n+2</tex> и <tex>4n+1</tex> одинаково записываются в двоичной записи, кроме последних двух битов, которые равны <tex>10</tex> и <tex>01</tex> соответственно и значит <tex>t_{4n+2}=t_{4n+1}</tex>. Так же заметим, что <tex>b_{2n+1}=1</tex>, так как <tex>2n+1</tex> и <tex>2n</tex> одинаково записываются в двоичной системе, кроме последнего бита и значит, что <tex>t_{2n+1}=\varphi(t_{2n})</tex>
 +
#* <tex>m</tex> нечетно и <tex>m \ge 5</tex>. Тогда <tex>b_{k+j}=b_{k+j+m}</tex> для <tex>1 \le j \le m</tex>. С <tex>m \ge 5</tex> существует <tex>j</tex>, такое что <tex>k+j=2</tex> по модулю <tex>4</tex>. Тогда для <tex>k+j</tex> точно известно, что <tex>b_{k+j}=0</tex>, но с другой стороны <tex>k+j+m</tex> - нечетно, значит <tex>b_{k+j+m}=1</tex>. Противоречие.
 +
#* <tex>m=3</tex>. Аналогично: <tex>b_{k+j}=b_{k+j+3}</tex> для <tex>1 \le j \le 3</tex>. Найдем <tex>j</tex>, чтобы <tex>k+j=2</tex> или <tex>k+j=3</tex> по модулю <tex>4</tex>. Если <tex>k+j=2</tex> по модулю <tex>4</tex>, то противоречие получается так же, как в предыдущем пункте. Рассмотрю <tex>k+j=3</tex> по модулю <tex>4</tex>, тогда <tex>b_{k+j}=1</tex>, но <tex>b_k+j+3=0</tex>. Это опять противоречие.
 +
#* <tex>m=1</tex>. Тогда <tex>t_k=t_{k+1}=t_{k+2}</tex> из чего следует, что <tex>t_{2n}=t_{2n+1}</tex> для <tex>n=k/2</tex>, но <tex>t_{2n}=\varphi(t_{2n+1}) \ne t_{2n+1}</tex>. Противоречие.
 +
 +
}}
  
 
== См. также ==
 
== См. также ==

Версия 15:11, 7 мая 2016

Определение:
Определим последовательность строк [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].

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

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

Очевидно что [math]t_{2n}=t_n[/math] и [math]t_{2n+1}=\varphi(t_n)[/math] для [math]n \ge 0[/math] Пусть существует две равные как строки подстрок строки [math]T_n[/math], имеющих пересекающиеся вхождения в [math]T_n[/math], тогда [math]T_n=ucxcxcv[/math], где [math]u,c,x,v[/math] — подстроки строки [math]T_n[/math]

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

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

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

См. также

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

Ссылки