129
правок
Изменения
Нет описания правки
{{Определение
|definition='''Строками Фибоначчи''' (англ. ''Fibostring'') являются называются строки над алфавитом <tex>\Sigma = \{a, b\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:
* <tex>h(a) = ab</tex>
* <tex>h(b) = a</tex>
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geqslant 2</tex>.
|proof=
'''База:''' При <tex>n = 2</tex> равенство очевидно<tex>f_2=ab=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>h^*(y) = \{y, x, xy, xyx, \ldots\}</tex>, и, наконец, определить <tex>n</tex>-ую обобщенную строку Фибоначчи как:
{{Определение
|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> в качестве префиксов.
}}
|proof= <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)) = 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>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+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\,\,mod \,\,2)</tex>.
}}
==Обратный морфизм==
{{Определение
|definition= Обратный морфизм <tex>h^{-1}</tex> определяется как отображение :* <tex>ab \rightarrow a</tex>, * <tex> a \rightarrow a </tex> (если после <tex>a</tex> следует <tex>b</tex>) или <tex> a \rightarrow b</tex> (в противном случае) .
}}
Обратный морфизм позволяет из строки <tex>f_n</tex> получить строку <tex>f_{n-1}</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 = Это следует из утверждения и теоремы выше .
}}
