Слово Фибоначчи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
(не показано 20 промежуточных версий этого же участника)
Строка 1: Строка 1:
<!---
 
==Определение==
 
 
{{Определение
 
{{Определение
|definition='''Морфизмом''' называется отображение <tex>h : \Sigma^* \rightarrow \Sigma^*</tex>, которое каждой букве <tex>\lambda</tex> из алфавита <tex>\Sigma</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>\Sigma^{+}</tex>,
+
|definition='''Строками Фибоначчи''' (англ. ''Fibostring'') называются строки над алфавитом <tex>\Sigma = \{x, y\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:
затем данное отображение распространяется на <tex>\Sigma^*</tex> следующим образом:
+
* <tex>h(x) = xy</tex>  
 
+
* <tex>h(y) = x</tex>
<tex>h(s) =
+
к строке <tex>s = y</tex>, т. е. последовательность <tex>f_n(x,y) = h^n(y)</tex>.
\left\{ \begin{array}{ll}
 
            h(s[1])h(s[2])...h(s[n]), & s \in \Sigma^+ \\
 
            \varepsilon, & s \in \Sigma^0 \\
 
        \end{array}
 
\right. </tex>
 
 
 
}}
 
 
 
Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>s</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(s)</tex> по следующему правилу: <br>
 
<ul><tex>h^{*}(s) = \{h^0(s), h^1(s),...\}</tex>. </ul>
 
где <tex>h^0(s) = s</tex> и для любого целого <tex>k \geqslant 1 :</tex> <tex> h^k(s) = h(h^{k-1}(s))</tex>.
 
 
 
'''Например''':
 
 
 
*<tex>\Sigma = \{a,b\}, h(a) = a, h(b) = ab</tex>.
 
 
 
*<tex>h^*(a) = \{a,a,...\}</tex>
 
 
 
*<tex>h^*(b) = \{b, ab, a^2b,..., a^kb...\}</tex>
 
 
 
--->
 
{{Определение
 
|definition='''Строками Фибоначчи''' (англ. ''Fibostring'') являются строки над алфавитом <tex>\Sigma = \{a, b\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:
 
* <tex>h(a) = ab</tex>  
 
* <tex>h(b) = a</tex>
 
к строке <tex>s = b</tex>, т.е. <tex>h^*(b)</tex>.
 
  
 
}}
 
}}
Строка 38: Строка 10:
 
Первые несколько строк Фибоначчи:  
 
Первые несколько строк Фибоначчи:  
  
* <tex>f_0 = b</tex>
+
* <tex>f_0 = y</tex>
* <tex>f_1 = a</tex>
+
* <tex>f_1 = x</tex>
* <tex>f_2 = ab</tex>
+
* <tex>f_2 = xy</tex>
* <tex>f_3 = aba</tex>
+
* <tex>f_3 = xyx</tex>
* <tex>f_4 = abaab</tex>
+
* <tex>f_4 = xyxxy</tex>
* <tex>f_5 = abaababa</tex>
+
* <tex>f_5 = xyxxyxyx</tex>
  
==Лемма==
+
==Рекуррентное соотношение для строк Фибоначчи==
 
{{Лемма
 
{{Лемма
 +
|about=1
 
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geqslant 2</tex>.
 
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geqslant 2</tex>.
 
|proof=
 
|proof=
Доказательство нетрудно получить методом математической индукции.  
+
Докажем методом математической индукции по <tex>f_n</tex>.
 +
 
 +
'''База:'''
 +
 
 +
: При <tex>n = 2</tex> выполняется <tex>f_2=xy=f_1f_0</tex>.
  
'''База:''' При <tex>n = 2</tex> равенство очевидно.
+
'''Переход:'''  
  
'''Переход:''' Пусть <tex>n > 2</tex> и <tex>f_n = f_{n-1}f_{n-2}</tex>. <tex>f_{n+1} = h(f_n) = h(f_{n-1}f_{n-2})</tex>. Так как отображение h {{---}} линейно (т.е. <tex>h(xy) = h(x)h(y)</tex>), то можно продолжить равенство:
+
:Пусть <tex>n > 2</tex> и <tex>f_n = f_{n-1}f_{n-2}</tex>.  
<tex>f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}</tex>.
+
:<tex>f_{n+1} = h(f_n) = h(f_{n-1}f_{n-2})</tex>.  
 +
:Так как отображение <tex>h</tex> {{---}} линейно (т.е. <tex>h(xy) = h(x)h(y)</tex>), то можно продолжить равенство:
 +
:<tex>f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}</tex>.
 
}}
 
}}
  
Строка 60: Строка 39:
  
  
==Обобщенная строка Фибоначчи. Связь с задачей о построении <tex>(\alpha, r)</tex>-исключений==
+
==Свойства строк Фибоначчи==
Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов <tex>a</tex> и <tex>b</tex> будем оперировать двумя произвольными строками <tex>x,y \in \Sigma^*</tex>:
 
*<tex>h(x) = xy</tex>
 
*<tex>h(y) = x</tex>
 
Таким образом "старый" морфизм будет частным случаем "нового" морфизма при <tex>x = a</tex> и <tex>y = b</tex>.
 
  
По аналогии можно вычислить <tex>h^*(y) = \{y, x, xy, xyx, \dots\}</tex>, и ,наконец, определить n-ую обобщенную строку Фибоначчи как:
 
 
{{Определение
 
{{Определение
|definition=Обобщенная строка Фибоначчи (англ. ''generalized Fibostring'') имеет вид <tex>f_n(x,y) = h^n(y)</tex>
+
|definition=Определим  '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' (англ. ''generalized infinite Fibostring'') как строку, содержащую все строки <tex>f_n(x,y), n \geqslant 0</tex> в качестве префиксов.
 
}}
 
}}
  
Первые несколько обобщенных строк имеют вид:
+
{{Лемма
*<tex>f_0(x,y) = y</tex>
+
|about = 2
*<tex>f_1(x,y) = x</tex>
+
|statement= Для любого целого <tex>k \geqslant 0</tex> выполняется <tex>f_n = f_{n-k}(f_{k+1},f_k)</tex>.
*<tex>f_2(x,y)= xy</tex>
+
|proof= <tex>f_n(x,y) = h^n(y) = h^{n-k}(h^k(y))</tex>
*<tex>f_3(x,y)= xyx</tex>
 
*<tex>f_4(x,y) = xyxxy</tex>
 
А также в общем случае:
 
*<tex>f_n(x,y) = f_{n-1}(x,y)f_{n-2}(x,y)</tex>
 
  
{{Определение
+
<tex>f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y)) </tex>
|definition=Определим  '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' (англ. ''generalized infinite Fibostring'') как строку, содержащую все строки <tex>f_n(x,y), n \geqslant 0</tex> в качестве префиксов
 
}}
 
  
Поскольку <tex>h^n(y) = h^{n-k}(h^k(y))</tex>, то <tex>f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y))</tex>, и, так как <tex>h^k(x) = h^{k+1}(y)</tex>, в итоге получаем:
+
Так как <tex>h^k(x)=h^{k+1}(y)</tex>, то <tex>f_n(x,y) = f_{n-k}(h^k(x),h^k(y)) = f_{n-k}(h^{k+1}(y),h^k(y))</tex>.
*<tex>f_n = f_{n-k}(f_{k+1},f_k)</tex>.
+
}}
 
'''Например''':
 
'''Например''':
<tex>f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)</tex>
+
<tex>f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)</tex>.
 +
 
 +
Это равенство работает также для <tex>f_{\infty}: f_{\infty} = f_{\infty}(f_{n+1},f_{n}) = f_{n+1}f_n f_{n+1} f_{n+1} f_n f_{n+1} f_n f_{n+1} \ldots</tex>.
  
Это равенство походит также и для <tex>f_{\infty}: f_{\infty} = f_{\infty}(f_{n+1},f_{n}) = f_{n+1}f_n f_{n+1} f_{n+1} f_n f_{n+1} f_n f_{n+1} \dots</tex>
 
 
{{Утверждение
 
{{Утверждение
|statement=Бесконечная строка Фибоначчи <tex>f_{\infty}</tex> является решением {{Acronym | задачи построения (2,4)-исключения| Требуется построить бесконечную строковую последовательность на алфавите размером 2, свободную от кратных подстрок порядка 4, но содержащую кратные подстроки порядков 2 и 3 }}
+
|about=1
}}
+
|statement = Для любого целого <tex>n</tex> выполняется <tex>f_nf_{n+1}  \neq f_{n+1}f_n</tex>.
<!-- >.
+
|proof = Докажем это утверждение методом математической индукции по <tex>f_n</tex>.
-->
 
 
 
<!--
 
==Теорема==
 
===Вспомогательные леммы и определения===
 
Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов <tex>a</tex> и <tex>b</tex> будем оперировать двумя произвольными строками <tex>x,y \in \Sigma^*</tex>:
 
*<tex>h(x) = xy</tex>
 
*<tex>h(y) = x</tex>
 
Таким образом "старый" морфизм будет частным случаем "нового" морфизма при <tex>x = a</tex> и <tex>y = b</tex>.
 
 
 
По аналогии можно вычислить <tex>h^*(y) = \{y, x, xy, xyx, \dots\}</tex>, и ,наконец, определить n-ую обобщенную строку Фибоначчи как:
 
{{Определение
 
|definition=Обобщенная строка Фибоначчи имеет вид <tex>f_n(x,y) = h^n(y)</tex>
 
}}
 
  
Первые несколько обобщенных строк имеют вид:
+
'''База:'''
*<tex>f_0(x,y) = y</tex>
+
:<tex>f_0f_1 \neq f_1f_0</tex>
*<tex>f_1(x,y) = x</tex>
 
*<tex>f_2(x,y)= xy</tex>
 
*<tex>f_3(x,y)= xyx</tex>
 
*<tex>f_4(x,y) = xyxxy</tex>
 
А также в общем случае:
 
*<tex>f_n(x,y) = f_{n-1}(x,y)f_{n-2}(x,y)</tex>
 
  
{{Определение
+
'''Переход:'''
|definition=Определим  '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' как строку, содержащую все строки <tex>f_n(x,y), n \geqslant 0</tex> в качестве префиксов
+
:<tex>f_nf_{n+1}=f_nf_nf_{n-1}=f_nf_{n-1}f_{n-2}f_{n-1}</tex>
 +
:<tex>f_{n+1}f_n=f_nf_{n-1}f_n=f_nf_{n-1}f_{n-1}f_{n-2}</tex>
 +
:Но то, что <tex> f_{n-2}f_{n-1} \neq f_{n-1}f_{n-2} </tex> было доказано ранее в ходе индукции.
 
}}
 
}}
 
Поскольку <tex>h^n(y) = h^{n-k}(h^k(y))</tex>, то <tex>f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y))</tex>, и, так как <tex>h^k(x) = h^{k+1}(y)</tex>, финально получаем:
 
*<tex>f_n = f_{n-k}(f_{k+1},f_k)</tex>.
 
'''Например''':
 
<tex>f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)</tex>
 
 
Это равенство походит также и для <tex>f_{\infty}: f_{\infty} = f_{\infty}(f_{n+1},f_{n}) = f_{n+1}f_n f_{n+1} f_{n+1} f_n f_{n+1} f_n f_{n+1} \dots</tex>
 
 
 
Так же имеют место быть 2 простые леммы.
 
 
{{Лемма
 
{{Лемма
|about = 1
+
|about = 3
|statement=Для любого целого <tex>n \geqslant 2</tex> выполняется равенство <tex>f^2_n = f_{n+1}f_{n-2}</tex>
+
|statement=Для любого целого <tex>n \geqslant 2</tex> выполняется равенство <tex>f^2_n = f_{n+1}f_{n-2}</tex>.
 +
|proof= <tex>f_{n+1}f_{n-2}=f_{n}f_{n-1}f_{n-2}=f_{n}f_{n}</tex>.
 
  }}
 
  }}
 
{{Лемма
 
{{Лемма
|about = 2
+
|about = 4
|statement= Для любого целого <tex>n \geqslant 3</tex> строка <tex>f_n</tex> имеет грани <tex>f_i</tex> для <tex>i = n-2, n-4,\dots,2-(n\,\,mod \,\,2)</tex>
+
|statement= Для любого целого <tex>n \geqslant 3</tex> строка <tex>f_n</tex> имеет [[Основные_определения,_связанные_со_строками#border|бордеры]] <tex>f_i</tex> для <tex>i = n-2, n-4,\ldots,2-(n \bmod 2)</tex>.
}}
+
|proof=
 
+
Будем последовательно применять лемму 1.
  
 +
<tex>f_n=f_{n-1}f_{n-2}=f_{n-2}f_{n-3}f_{n-2}</tex>. Таким образом, <tex>f_{n-2}</tex> является бордером.
  
 +
Далее, <tex>f_n=f_{n-3}f_{n-3}f_{n-3}f_{n-4}=f_{n-4}f_{n-5}\ldots f_{n-4} </tex>. Получили, что <tex>f_{n-4}</tex> также является бордером.
  
 +
Продолжая выполнять это преобразование, докажем лемму для всех заданных <tex>i</tex>.
 +
}}
 +
{{Утверждение
 +
|about=2
 +
|statement= В <tex>f_n(x,y)</tex> не может содержаться подстроки <tex>x^3</tex> или <tex>y^2</tex>.
 +
|proof = Докажем для <tex>x^3</tex> методом математической индукции по <tex>f_n</tex>.
  
 +
'''База:'''
 +
:<tex>f_0=y,f_1=x</tex>  не содержат <tex>x^3</tex>
 +
'''Переход:'''
 +
:Пусть <tex>n \geqslant 2</tex>, тогда <tex>f_n = f_{n-1}f_{n-2}</tex>.
 +
:Так как <tex>f_{n-1}</tex> и <tex>f_{n-2}</tex> не содержат <tex>x^3</tex>, то такая кратная строка может появиться только на границе строк <tex>f_{n-1}</tex> и <tex>f_{n-2}</tex>.
 +
:А <tex>f_{n-2}</tex> равно либо  <tex>x</tex>, либо  <tex>y</tex>, либо начинается с <tex>xy</tex> (при <tex>n \geqslant 4</tex>).
 +
:Таким образом, достаточно доказать, что последние два символа <tex>f_{n-1}</tex> не равны <tex>xx</tex>.
 +
:Это выполняется согласно лемме 4, по которой либо <tex>xy</tex>, либо <tex>xyx</tex> является бордером (в зависимости от четности длины строки).
 +
}}
 +
==Обратный морфизм==
 +
{{Определение
 +
|definition= '''Обратный морфизм''' <tex>h^{-1}</tex> определяется как отображение:
 +
* <tex>h^{-1}(xy) = x</tex>,
 +
* <tex>h^{-1}(x) =
 +
\left\{ \begin{array}{ll}
 +
            y, \overline{xx}\\
 +
            x, \text{otherwise}\\
 +
        \end{array}
 +
\right. </tex>
 +
Здесь <tex>\overline{xx}</tex> обозначает, что после этого вхождения <tex>x</tex> в строке опять следует <tex>x</tex>.
  
 +
}}
 +
Обратный морфизм позволяет из строки <tex>f_n</tex> получить строку <tex>f_{n-1}</tex>.
  
 +
'''Пример''':
 +
: <tex>f_4=xyxxy</tex>.
 +
: Будем последовательно применять морфизм:
 +
: Префикс <tex>xy</tex> переходит в <tex>x</tex>, центральный <tex>x</tex> переходит в <tex>y</tex>, а суффикс <tex>xy</tex> также переходит в <tex>x</tex>.
 +
: Получили <tex>xyx = f_3</tex>.
 +
== Связь с задачей о построении исключений==
 +
{{Утверждение
 +
|about=3
 +
|statement= Для любого целого <tex>n \geqslant 7</tex> <tex>f_n</tex> содержит куб некоторой подстроки.
 +
|proof = Строка <tex>f_7 = xyxxyxyxxyxxyxyxxyxyx</tex> содержит подстроку <tex>xyxxyxxyx = (xyx)^3 </tex> и является префиксом <tex>f_n</tex> для <tex>n \geqslant 7</tex>.
 +
}}
 
{{Теорема
 
{{Теорема
|statement=Все строки Фибоначчи <tex>f_n</tex> при <tex>n \geqslant 7</tex> содержат кубы, но ни одна строка Фибоначчи не содержит кратных подстрок четвертого порядка
+
|about=1
|proof=  
+
|statement= Никакая строка <tex>f_n</tex> не содержит подстроки кратности <tex>4</tex>.
 +
}}
 +
{{Утверждение
 +
|about= 4
 +
|statement=Бесконечная строка Фибоначчи <tex>f_{\infty}</tex> является решением {{Acronym | задачи построения <tex>(2,4)</tex>-исключения| Требуется построить бесконечную строковую последовательность на алфавите размером 2, свободную от кратных подстрок порядка 4, но содержащую кратные подстроки порядков 2 и 3.}}
 +
|proof = Это следует из утверждения и теоремы выше.
 
}}
 
}}
  
-->
 
 
== См. также ==
 
== См. также ==
 
* [[Слово Туэ-Морса]]
 
* [[Слово Туэ-Морса]]
  
== Источники ==
+
== Источники информации==
* Билл Смит «Методы и алгоритмы вычислений на строках», издательство «Вильямс», 2006 {{---}} стр. 100-107
+
* Билл Смит «Методы и алгоритмы вычислений на строках» {{---}} издательство «Вильямс» {{---}} 2006 {{---}} стр. 100-107
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Версия 02:42, 9 июня 2016

Определение:
Строками Фибоначчи (англ. Fibostring) называются строки над алфавитом [math]\Sigma = \{x, y\}[/math], полученные последовательным применением морфизма [math]h[/math]:
  • [math]h(x) = xy[/math]
  • [math]h(y) = x[/math]
к строке [math]s = y[/math], т. е. последовательность [math]f_n(x,y) = h^n(y)[/math].


Примеры

Первые несколько строк Фибоначчи:

  • [math]f_0 = y[/math]
  • [math]f_1 = x[/math]
  • [math]f_2 = xy[/math]
  • [math]f_3 = xyx[/math]
  • [math]f_4 = xyxxy[/math]
  • [math]f_5 = xyxxyxyx[/math]

Рекуррентное соотношение для строк Фибоначчи

Лемма (1):
Строки Фибоначчи удовлетворяют рекуррентному соотношению [math]f_n = f_{n-1}f_{n-2}, n \geqslant 2[/math].
Доказательство:
[math]\triangleright[/math]

Докажем методом математической индукции по [math]f_n[/math].

База:

При [math]n = 2[/math] выполняется [math]f_2=xy=f_1f_0[/math].

Переход:

Пусть [math]n \gt 2[/math] и [math]f_n = f_{n-1}f_{n-2}[/math].
[math]f_{n+1} = h(f_n) = h(f_{n-1}f_{n-2})[/math].
Так как отображение [math]h[/math] — линейно (т.е. [math]h(xy) = h(x)h(y)[/math]), то можно продолжить равенство:
[math]f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}[/math].
[math]\triangleleft[/math]

Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.


Свойства строк Фибоначчи

Определение:
Определим бесконечную обобщенную строку Фибоначчи [math]f_{\infty}(x,y)[/math] (англ. generalized infinite Fibostring) как строку, содержащую все строки [math]f_n(x,y), n \geqslant 0[/math] в качестве префиксов.


Лемма (2):
Для любого целого [math]k \geqslant 0[/math] выполняется [math]f_n = f_{n-k}(f_{k+1},f_k)[/math].
Доказательство:
[math]\triangleright[/math]

[math]f_n(x,y) = h^n(y) = h^{n-k}(h^k(y))[/math]

[math]f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y)) [/math]

Так как [math]h^k(x)=h^{k+1}(y)[/math], то [math]f_n(x,y) = f_{n-k}(h^k(x),h^k(y)) = f_{n-k}(h^{k+1}(y),h^k(y))[/math].
[math]\triangleleft[/math]

Например: [math]f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)[/math].

Это равенство работает также для [math]f_{\infty}: f_{\infty} = f_{\infty}(f_{n+1},f_{n}) = f_{n+1}f_n f_{n+1} f_{n+1} f_n f_{n+1} f_n f_{n+1} \ldots[/math].

Утверждение (1):
Для любого целого [math]n[/math] выполняется [math]f_nf_{n+1} \neq f_{n+1}f_n[/math].
[math]\triangleright[/math]

Докажем это утверждение методом математической индукции по [math]f_n[/math].

База:

[math]f_0f_1 \neq f_1f_0[/math]

Переход:

[math]f_nf_{n+1}=f_nf_nf_{n-1}=f_nf_{n-1}f_{n-2}f_{n-1}[/math]
[math]f_{n+1}f_n=f_nf_{n-1}f_n=f_nf_{n-1}f_{n-1}f_{n-2}[/math]
Но то, что [math] f_{n-2}f_{n-1} \neq f_{n-1}f_{n-2} [/math] было доказано ранее в ходе индукции.
[math]\triangleleft[/math]
Лемма (3):
Для любого целого [math]n \geqslant 2[/math] выполняется равенство [math]f^2_n = f_{n+1}f_{n-2}[/math].
Доказательство:
[math]\triangleright[/math]
[math]f_{n+1}f_{n-2}=f_{n}f_{n-1}f_{n-2}=f_{n}f_{n}[/math].
[math]\triangleleft[/math]
Лемма (4):
Для любого целого [math]n \geqslant 3[/math] строка [math]f_n[/math] имеет бордеры [math]f_i[/math] для [math]i = n-2, n-4,\ldots,2-(n \bmod 2)[/math].
Доказательство:
[math]\triangleright[/math]

Будем последовательно применять лемму 1.

[math]f_n=f_{n-1}f_{n-2}=f_{n-2}f_{n-3}f_{n-2}[/math]. Таким образом, [math]f_{n-2}[/math] является бордером.

Далее, [math]f_n=f_{n-3}f_{n-3}f_{n-3}f_{n-4}=f_{n-4}f_{n-5}\ldots f_{n-4} [/math]. Получили, что [math]f_{n-4}[/math] также является бордером.

Продолжая выполнять это преобразование, докажем лемму для всех заданных [math]i[/math].
[math]\triangleleft[/math]
Утверждение (2):
В [math]f_n(x,y)[/math] не может содержаться подстроки [math]x^3[/math] или [math]y^2[/math].
[math]\triangleright[/math]

Докажем для [math]x^3[/math] методом математической индукции по [math]f_n[/math].

База:

[math]f_0=y,f_1=x[/math] не содержат [math]x^3[/math]

Переход:

Пусть [math]n \geqslant 2[/math], тогда [math]f_n = f_{n-1}f_{n-2}[/math].
Так как [math]f_{n-1}[/math] и [math]f_{n-2}[/math] не содержат [math]x^3[/math], то такая кратная строка может появиться только на границе строк [math]f_{n-1}[/math] и [math]f_{n-2}[/math].
А [math]f_{n-2}[/math] равно либо [math]x[/math], либо [math]y[/math], либо начинается с [math]xy[/math] (при [math]n \geqslant 4[/math]).
Таким образом, достаточно доказать, что последние два символа [math]f_{n-1}[/math] не равны [math]xx[/math].
Это выполняется согласно лемме 4, по которой либо [math]xy[/math], либо [math]xyx[/math] является бордером (в зависимости от четности длины строки).
[math]\triangleleft[/math]

Обратный морфизм

Определение:
Обратный морфизм [math]h^{-1}[/math] определяется как отображение:
  • [math]h^{-1}(xy) = x[/math],
  • [math]h^{-1}(x) = \left\{ \begin{array}{ll} y, \overline{xx}\\ x, \text{otherwise}\\ \end{array} \right. [/math]
Здесь [math]\overline{xx}[/math] обозначает, что после этого вхождения [math]x[/math] в строке опять следует [math]x[/math].

Обратный морфизм позволяет из строки [math]f_n[/math] получить строку [math]f_{n-1}[/math].

Пример:

[math]f_4=xyxxy[/math].
Будем последовательно применять морфизм:
Префикс [math]xy[/math] переходит в [math]x[/math], центральный [math]x[/math] переходит в [math]y[/math], а суффикс [math]xy[/math] также переходит в [math]x[/math].
Получили [math]xyx = f_3[/math].

Связь с задачей о построении исключений

Утверждение (3):
Для любого целого [math]n \geqslant 7[/math] [math]f_n[/math] содержит куб некоторой подстроки.
[math]\triangleright[/math]
Строка [math]f_7 = xyxxyxyxxyxxyxyxxyxyx[/math] содержит подстроку [math]xyxxyxxyx = (xyx)^3 [/math] и является префиксом [math]f_n[/math] для [math]n \geqslant 7[/math].
[math]\triangleleft[/math]
Теорема (1):
Никакая строка [math]f_n[/math] не содержит подстроки кратности [math]4[/math].
Утверждение (4):
Бесконечная строка Фибоначчи [math]f_{\infty}[/math] является решением задачи построения [math](2,4)[/math]-исключения
[math]\triangleright[/math]
Это следует из утверждения и теоремы выше.
[math]\triangleleft[/math]

См. также

Источники информации

  • Билл Смит «Методы и алгоритмы вычислений на строках» — издательство «Вильямс» — 2006 — стр. 100-107