Изменения

|definition='''МорфизмомСтроками Фибоначчи''' называется отображение <tex>h</tex>, которое каждой букве (англ. ''Fibostring'') называются строки над алфавитом <tex>\lambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(Sigma = \lambda)</tex> из множества <tex>A^{+x, y\}</tex>, а каждой строке полученные последовательным применением морфизма <tex>x</tex> из <tex>A^+h</tex> ставит в соответсвие строку из <tex>A^+</tex> по следующему правилу :* <tex>h(x) = h(x[1])h(x[2])...h(x[n])xy</tex> , где * <tex>h(y) = x[1], x[2], \dots, x[n]</tex> уже являются элементами к строке <tex>As = y</tex>, т. е.*последовательность <tex>f_n(x,y) = h : A \rightarrow A^+n(y)</tex>.*<tex>h : A^+ \rightarrow A^+</tex>

Любой морфизм ==Примеры==Первые несколько строк Фибоначчи:  * <tex>hf_0 = y</tex> можно применять к исходной строке * <tex>x_0f_1 = x</tex> любое число раз, тем самым генерируя последовательность итераций * <tex>h^{*}(x_0)f_2 = xy</tex> по следующему правилу: <br>* <ultex>f_3 = xyx</tex>h^{*}(x_0) = \{h^0(x_0), h^1(x_0),...\}</tex>. f_4 = xyxxy</ultex>где * <tex>h^0(x_0) f_5 = x_0xyxxyxyx</tex> и  ==Рекуррентное соотношение для любого целого строк Фибоначчи=={{Лемма|about=1|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>k f_n = f_{n-1}f_{n-2}, n \geq 1 :geqslant 2</tex> .|proof=Докажем методом математической индукции по <tex> h^k(x_0) = h(h^{k-1}(x_0))f_n</tex>.  '''База:'''

: При <tex>n = 2</tex> выполняется <tex>f_2=xy=f_1f_0</tex>. '''НапримерПереход:''':

*:Пусть <tex>A n > 2</tex> и <tex>f_n = f_{n-1}f_{n-2}</tex>. :<tex>f_{n+1} = h(f_n) = \h(f_{a,b\n-1}f_{n-2})</tex>. :Так как отображение <tex>h</tex> {{---}}, линейно (т.е. <tex>h(axy) = ah(x)h(y)</tex>), то можно продолжить равенство::<tex>f_{n+1} = h(bf_{n-1})h(f_{n-2}) = abf_{n}f_{n-1}</tex>. }}

*<tex>h^*(a) = \{aТакже можно заметить,a,..что длины строк Фибоначчи совпадают с числами Фибоначчи.\}</tex>

|definition=Определим '''Строками бесконечную обобщенную строку Фибоначчи<tex>f_{\infty}(x,y)</tex>''' (англ. ''generalized infinite Fibostring'' являются ) как строку, содержащую все строки<tex>f_n(x,y), полученные последовательным применением морфизма n \geqslant 0</tex> в качестве префиксов.}} {{Лемма|about = 2|statement= Для любого целого <tex>hk \geqslant 0</tex> к строке выполняется <tex>x_0 f_n = bf_{n-k}(f_{k+1},f_k)</tex>, т.е. |proof= <tex>f_n(x,y) = h^n(y) = h^{n-k}(h^*k(by))</tex>.* <tex>A f_n(x,y) = \h^k(f_{an-k}(x,b\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(af_3, f_2) = ab(xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)</tex> . * Это равенство работает также для <tex>hf_{\infty}: f_{\infty} = f_{\infty}(bf_{n+1},f_{n}) = af_{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_0 = bi</tex>.}}{{Утверждение|about=2* |statement= В <tex>f_1 = af_n(x,y)</tex>* не может содержаться подстроки <tex>f_2 = abx^3</tex>* или <tex>f_3 = abay^2</tex>.* |proof = Докажем для <tex>f_4 = abaabx^3</tex>* методом математической индукции по <tex>f_5 = abaababaf_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_{Лемма|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению n-2}</tex> не содержат <tex>x^3</tex>, то такая кратная строка может появиться только на границе строк <tex>f_n = 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 \geq 2geqslant 4</tex>).:Таким образом, достаточно доказать, что последние два символа <tex>f_{n-1}</tex> не равны <tex>xx</tex>.:Это выполняется согласно лемме 4, по которой либо <tex>xy</tex>, либо <tex>xyx</tex>является бордером (в зависимости от четности длины строки).}}==Обратный морфизм=={{Определение|proofdefinition='''Обратный морфизм''' <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 = 2-1}</tex> равенство очевидно.

'''Переход:Пример''' Пусть :: <tex>f_4=xyxxy</tex>n . : Будем последовательно применять морфизм:: Префикс <tex>xy</tex> переходит в <tex>x</tex>, центральный <tex>x</tex> переходит в <tex>y</tex>, а суффикс <tex> 2xy</tex> и также переходит в <tex>f_n = f_{n-1}f_{n-2}x</tex>. : Получили <tex>xyx = f_3</tex>f_{n+1} .== Связь с задачей о построении исключений= h(f_n) = h(f_{n-1}f_{Утверждение|about=3|statement= Для любого целого <tex>n-2})\geqslant 7</tex> <tex>f_n</tex>содержит куб некоторой подстроки. Т.к. h {{---}} линейна (т.е. |proof = Строка <tex>f_7 = xyxxyxyxxyxxyxyxxyxyx</tex> содержит подстроку <tex>h(xy) xyxxyxxyx = h(x)h(yxyx)^3 </tex> и является префиксом <tex>f_n</tex>), то можно продолжить равенство:для <tex>f_{n+1\geqslant 7</tex>.}} {{Теорема|about= h(f_{n-1|statement= Никакая строка <tex>f_n</tex> не содержит подстроки кратности <tex>4</tex>.})h(f_}{{n-2}) Утверждение|about= 4|statement= Бесконечная строка Фибоначчи <tex>f_{n\infty}f_</tex> является решением {{n-1}Acronym | задачи построения <tex>(2,4)</tex>-исключения| Требуется построить бесконечную строковую последовательность на алфавите размером 2, свободную от кратных подстрок порядка 4, но содержащую кратные подстроки порядков 2 и 3.}}|proof = Это следует из утверждения и теоремы выше.

Также нетрудно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи== См.также ==* [[Слово Туэ-Морса]]

== Литература Источники информации==* Билл Смит. Методы «Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", строках» {{---}} издательство «Вильямс» {{---}} 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5{{-8459-1081-1 (рус}} стр.)100-107