Изменения

|definition='''Морфизмом''' называется отображение <tex>h : \Sigma^* \rightarrow \Sigma^*</tex>, которое каждой букве <tex>\lambda</tex> из алфавита <tex>\Sigma</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>\Sigma^{+}</tex>,затем данное отображение распространяется на <tex>\Sigma^*</tex> следующим образом: <tex>h(s) = \left\{ \begin{array}{ll} h(s[1])h(s[2])...h(s[n]), & s \in \Sigma^+ \\ \varepsilon, & s \in \Sigma^0 \\ \end{array}\right. </tex> }} Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>s</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(s)</tex> по следующему правилу: <br><ul><tex>h^{*}(s) = \{h^0(s), h^1(s),...\}</tex>. </ul>где <tex>h^0(s) = s</tex> и для любого целого <tex>k \geqslant 1 :</tex> <tex> h^k(s) = h(h^{k-1}(s))</tex>.  '''Например''': *<tex>\Sigma = \{a,b\}, h(a) = a, h(b) = ab</tex>.  *<tex>h^*(a) = \{a,a,...\}</tex>  *<tex>h^*(b) = \{b, ab, a^2b,..., a^kb...\}</tex> --->{{Определение|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>f_2=xy=f_1f_0</tex>.

'''БазаПереход:''' При <tex>n = 2</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>(\alpha, r)</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>.

|definition=Обобщенная строка Определим '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' (англ. ''generalized infinite Fibostring'') имеет вид как строку, содержащую все строки <tex>f_n(x,y) = h^, n(y)\geqslant 0</tex>в качестве префиксов.

Первые несколько обобщенных строк имеют вид:{{Лемма*<tex>f_0(x,y) |about = y</tex>2*|statement= Для любого целого <tex>f_1(x,y) = xk \geqslant 0</tex>*выполняется <tex>f_2(x,y)f_n = xy</tex>*<tex>f_3f_{n-k}(xf_{k+1},yf_k)= xyx</tex>.*<tex>f_4(x,y) |proof= xyxxy</tex>А также в общем случае:*<tex>f_n(x,y) = f_{h^n-1}(x,y)f_= h^{n-2k}(x,h^k(y))</tex>

{{Определение|definition=Определим '''бесконечную обобщенную строку Фибоначчи <tex>f_n(x,y) = h^k(f_{\inftyn-k}(x,y)</tex>''' ) = f_{n-k}(h^k(англ. ''generalized infinite Fibostring''x) как строку, содержащую все строки <tex>f_nh^k(x,y), n \geqslant 0) </tex> в качестве префиксов}}

Поскольку Так как <tex>h^nk(yx) = h^{n-k+1}(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^= f_{n-k}(x) = h^{k+1}(y)</tex>, в итоге получаем:*<tex>f_n = f_{n-h^k}(f_{k+1},f_ky))</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>.

|statementabout=Бесконечная строка Фибоначчи <tex>f_{\infty}</tex> является решением {{Acronym 1| задачи построения (2,4)-исключения| Требуется построить бесконечную строковую последовательность на алфавите размером 2, свободную от кратных подстрок порядка 4, но содержащую кратные подстроки порядков 2 и 3 }} }}<!-- >.--> <!--==Теорема==statement ===Вспомогательные леммы и определения===Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов Для любого целого <tex>an</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) = f_nf_{n+1} \neq f_{y, x, xy, xyx, \dots\n+1}f_n</tex>, и ,наконец, определить n-ую обобщенную строку Фибоначчи как:{{Определение.|definitionproof =Обобщенная строка Фибоначчи имеет вид Докажем это утверждение методом математической индукции по <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)f_0f_1 \neq f_1f_0</tex>

{{Определение|definition=Определим '''бесконечную обобщенную строку Фибоначчи Переход:''' :<tex>f_nf_{n+1}=f_nf_nf_{n-1}=f_nf_{n-1}f_{\inftyn-2}f_{n-1}(x,y)</tex>''' как строку, содержащую все строки :<tex>f_{n+1}f_n=f_nf_{n-1}f_n(x,y)=f_nf_{n-1}f_{n-1}f_{n-2}</tex>:Но то, что <tex> f_{n-2}f_{n -1} \geqslant 0neq f_{n-1}f_{n-2} </tex> было доказано ранее в качестве префиксовходе индукции.

|about = 13|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 = 24|statement= Для любого целого <tex>n \geqslant 3</tex> строка <tex>f_n</tex> имеет грани [[Основные_определения,_связанные_со_строками#border|бордеры]] <tex>f_i</tex> для <tex>i = n-2, n-4,\dotsldots,2-(n\,\,mod \,\,bmod 2)</tex>.}}|proof= Будем последовательно применять лемму 1.

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

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