129
правок
Изменения
м
Нет описания правки
{{Определение
|definition='''Строками Фибоначчи называется ''' (англ. ''Fibostring'') называются строки, удовлетворяющие следующим условиям:* над алфавитом <tex>F_0 \Sigma = \epsilon{x, y\}</tex>* , полученные последовательным применением морфизма <tex>F_1 = bh</tex>:* <tex>F_2 h(x) = axy</tex>* <tex>F_n h(y) = F_{n-1}F{n-2}x</tex> (т.е. конкатенации строк к строке <tex>F_{n-1}s = y</tex> и , т. е. последовательность <tex>F_{f_n(x,y) = h^n-2}(y)</tex>).
}}
==Примеры==
Первые несколько строк Фибоначчи:
* <tex>f_0 = y</tex>
* <tex>f_1 = x</tex>
* <tex>f_2 = xy</tex>
* <tex>f_3 = xyx</tex>
* <tex>f_4 = xyxxy</tex>
* <tex>f_5 = xyxxyxyx</tex>
==Рекуррентное соотношение для строк Фибоначчи==
{{Лемма
|about=1
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geqslant 2</tex>.
|proof=
Докажем методом математической индукции по <tex>f_n</tex>.
'''База:'''
: При <tex>n = 2</tex> выполняется <tex>f_2=xy=f_1f_0</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>.
:Так как отображение <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>.
}}
Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
==Свойства строк Фибоначчи==
{{Определение
|definition=Определим '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' (англ. ''generalized infinite Fibostring'') как строку, содержащую все строки <tex>f_n(x,y), n \geqslant 0</tex> в качестве префиксов.
}}
{{Лемма
|about = 2
|statement= Для любого целого <tex>k \geqslant 0</tex> выполняется <tex>f_n = f_{n-k}(f_{k+1},f_k)</tex>.
|proof= <tex>f_n(x,y) = 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(x,y) = f_{n-k}(h^k(x),h^k(y)) = f_{n-k}(h^{k+1}(y),h^k(y))</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>.
{{Утверждение
|about=1
|statement = Для любого целого <tex>n</tex> выполняется <tex>f_nf_{n+1} \neq f_{n+1}f_n</tex>.
|proof = Докажем это утверждение методом математической индукции по <tex>f_n</tex>.
'''База:'''
:<tex>f_0f_1 \neq f_1f_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> было доказано ранее в ходе индукции.
}}
{{Лемма
|about = 3
|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 = 4
|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>.
}}
{{Теорема
|about=1
|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
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
