129
правок
Изменения
Нет описания правки
* <tex>h(x) = xy</tex>
* <tex>h(y) = x</tex>
к строке <tex>s = y</tex>, т. е. последовательность <tex>f_n(x,y) = h^n(by)</tex>.
}}
Первые несколько строк Фибоначчи:
* <tex>f_0 = by</tex>* <tex>f_1 = ax</tex>* <tex>f_2 = abxy</tex>* <tex>f_3 = abaxyx</tex>* <tex>f_4 = abaabxyxxy</tex>* <tex>f_5 = abaababaxyxxyxyx</tex>
==Рекуррентное соотношение для строк Фибоначчи==
'''База:'''
*: При <tex>n = 2</tex> <tex>f_2=abxy=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>.
Это равенство работает также для <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
|proof = Докажем это утверждение методом математической индукции.
|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\,\,mod \,\,2)</tex>.
|proof=
}}
{{Утверждение
|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>ab \rightarrow a</tex>,
* <tex>a \rightarrow \left\{ \begin{array}{ll} a , \overline{ab}\\ b, \text{otherwise}\\ \end{array}\right. </tex> (если после Здесь <tex>a\overline{ab}</tex> следует обозначает, что после этого вхождения <tex>ba</tex>) или в строке следует <tex> a \rightarrow b</tex> (в противном случае).
}}
Обратный морфизм позволяет из строки <tex>f_n</tex> получить строку <tex>f_{n-1}</tex>.
