Изменения

|definition='''Строками Фибоначчи''' (англ. ''Fibostring'') являются называются строки над алфавитом <tex>\Sigma = \{ax, by\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:* <tex>h(ax) = abxy</tex> * <tex>h(by) = ax</tex>к строке <tex>s = by</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>f_n</tex>.

'''База:''' При <tex>n = 2</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>.

==Обобщенная строка Фибоначчи==Начнем обобщение идеи Свойства строк Фибоначчи следующим образом. Вместо отдельных символов <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, \ldots\}</tex>, и, наконец, определить <tex>n</tex>-ую обобщенную строку Фибоначчи как:{{Определение|definition=Обобщенная строка Фибоначчи (англ. ''generalized Fibostring'') имеет вид <tex>f_n(x,y) = h^n(y)</tex>}} Первые несколько обобщенных строк имеют вид:*<tex>f_0(x,y) = y</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>''' (англ. ''generalized infinite Fibostring'') как строку, содержащую все строки <tex>f_n(x,y), n \geqslant 0</tex> в качестве префиксов.

|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>.

|statement= В <tex>f_n(x,y)</tex> не может содержаться подстроки <tex>x^3</tex> или <tex>y^2</tex>}}{{Утверждение|about=2|statement = Для любого целого <tex>n</tex> выполняется <tex>f_nf_{n+1} \neq f_{n+1}f_n</tex>.|proof = Докажем это утверждение методом математической индукциипо <tex>f_n</tex>.

1) '''База. :''' :<tex>f_0f_1 \neq f_1f_0</tex>

2) '''Переход. :''' :<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> было доказано ранее в ходе индукции.

|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>.

|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> является бордером. Далее,mod <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> также является бордером. Продолжая выполнять это преобразование,2)докажем лемму для всех заданных <tex>i</tex>.

|definition= '''Обратный морфизм ''' <tex>h^{-1}</tex> определяется как отображение :* <tex>ab \rightarrow ah^{-1}(xy) = x</tex>, * <tex> a h^{-1}(x) = \left\{ \begin{array}{ll} y, \rightarrow a overline{xx}\\ x, \text{otherwise}\\ \end{array}\right. </tex> (если после Здесь <tex>a\overline{xx}</tex> следует обозначает, что после этого вхождения <tex>bx</tex>) или в строке опять следует <tex> a \rightarrow bx</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>.

|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>4</tex>.

|statement=Бесконечная строка Фибоначчи <tex>f_{\infty}</tex> является решением {{Acronym | задачи построения <tex>(2,4)</tex>-исключения| Требуется построить бесконечную строковую последовательность на алфавите размером 2, свободную от кратных подстрок порядка 4, но содержащую кратные подстроки порядков 2 и 3 .}}|proof = Это следует из утверждения и теоремы выше .

== Источники информации==* Билл Смит «Методы и алгоритмы вычислений на строках», {{---}} издательство «Вильямс», {{---}} 2006 {{---}} стр. 100-107