Слово Фибоначчи

Определение:

Строками Фибоначчи (англ. Fibostring) называются строки над алфавитом [math]\Sigma = \{x, y\}[/math], полученные последовательным применением морфизма [math]h[/math]: [math]h(x) = xy[/math] [math]h(y) = x[/math] к строке [math]s = y[/math], т. е. последовательность [math]f_n(x,y) = h^n(y)[/math].

Примеры

Первые несколько строк Фибоначчи:

• [math]f_0 = y[/math]
• [math]f_1 = x[/math]
• [math]f_2 = xy[/math]
• [math]f_3 = xyx[/math]
• [math]f_4 = xyxxy[/math]
• [math]f_5 = xyxxyxyx[/math]

Рекуррентное соотношение для строк Фибоначчи

Лемма (1):

Строки Фибоначчи удовлетворяют рекуррентному соотношению [math]f_n = f_{n-1}f_{n-2}, n \geqslant 2[/math].

Доказательство:

[math]\triangleright[/math]

Докажем методом математической индукции по [math]f_n[/math]. База: При [math]n = 2[/math] выполняется [math]f_2=xy=f_1f_0[/math]. Переход: Пусть [math]n \gt 2[/math] и [math]f_n = f_{n-1}f_{n-2}[/math]. [math]f_{n+1} = h(f_n) = h(f_{n-1}f_{n-2})[/math]. Так как отображение [math]h[/math] — линейно (т.е. [math]h(xy) = h(x)h(y)[/math]), то можно продолжить равенство: [math]f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}[/math].

[math]\triangleleft[/math]

Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.

Свойства строк Фибоначчи

Определение:

Определим бесконечную обобщенную строку Фибоначчи [math]f_{\infty}(x,y)[/math] (англ. generalized infinite Fibostring) как строку, содержащую все строки [math]f_n(x,y), n \geqslant 0[/math] в качестве префиксов.

Лемма (2):

Для любого целого [math]k \geqslant 0[/math] выполняется [math]f_n = f_{n-k}(f_{k+1},f_k)[/math].

Доказательство:

[math]\triangleright[/math]

[math]f_n(x,y) = h^n(y) = h^{n-k}(h^k(y))[/math] [math]f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y)) [/math] Так как [math]h^k(x)=h^{k+1}(y)[/math], то [math]f_n(x,y) = f_{n-k}(h^k(x),h^k(y)) = f_{n-k}(h^{k+1}(y),h^k(y))[/math].

[math]\triangleleft[/math]

Например: [math]f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)[/math].

Это равенство работает также для [math]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[/math].

Утверждение (1):

Для любого целого [math]n[/math] выполняется [math]f_nf_{n+1} \neq f_{n+1}f_n[/math].

[math]\triangleright[/math]

Докажем это утверждение методом математической индукции по [math]f_n[/math]. База: [math]f_0f_1 \neq f_1f_0[/math] Переход: [math]f_nf_{n+1}=f_nf_nf_{n-1}=f_nf_{n-1}f_{n-2}f_{n-1}[/math] [math]f_{n+1}f_n=f_nf_{n-1}f_n=f_nf_{n-1}f_{n-1}f_{n-2}[/math] Но то, что [math] f_{n-2}f_{n-1} \neq f_{n-1}f_{n-2} [/math] было доказано ранее в ходе индукции.

[math]\triangleleft[/math]

Лемма (3):

Для любого целого [math]n \geqslant 2[/math] выполняется равенство [math]f^2_n = f_{n+1}f_{n-2}[/math].

Доказательство:

[math]\triangleright[/math]

[math]f_{n+1}f_{n-2}=f_{n}f_{n-1}f_{n-2}=f_{n}f_{n}[/math].

[math]\triangleleft[/math]

Лемма (4):

Для любого целого [math]n \geqslant 3[/math] строка [math]f_n[/math] имеет бордеры [math]f_i[/math] для [math]i = n-2, n-4,\ldots,2-(n \bmod 2)[/math].

Доказательство:

[math]\triangleright[/math]

Будем последовательно применять лемму 1. [math]f_n=f_{n-1}f_{n-2}=f_{n-2}f_{n-3}f_{n-2}[/math]. Таким образом, [math]f_{n-2}[/math] является бордером. Далее, [math]f_n=f_{n-3}f_{n-3}f_{n-3}f_{n-4}=f_{n-4}f_{n-5}\ldots f_{n-4} [/math]. Получили, что [math]f_{n-4}[/math] также является бордером. Продолжая выполнять это преобразование, докажем лемму для всех заданных [math]i[/math].

[math]\triangleleft[/math]

Утверждение (2):

В [math]f_n(x,y)[/math] не может содержаться подстроки [math]x^3[/math] или [math]y^2[/math].

[math]\triangleright[/math]

Докажем для [math]x^3[/math] методом математической индукции по [math]f_n[/math]. База: [math]f_0=y,f_1=x[/math] не содержат [math]x^3[/math] Переход: Пусть [math]n \geqslant 2[/math], тогда [math]f_n = f_{n-1}f_{n-2}[/math]. Так как [math]f_{n-1}[/math] и [math]f_{n-2}[/math] не содержат [math]x^3[/math], то такая кратная строка может появиться только на границе строк [math]f_{n-1}[/math] и [math]f_{n-2}[/math]. А [math]f_{n-2}[/math] равно либо [math]x[/math], либо [math]y[/math], либо начинается с [math]xy[/math] (при [math]n \geqslant 4[/math]). Таким образом, достаточно доказать, что последние два символа [math]f_{n-1}[/math] не равны [math]xx[/math]. Это выполняется согласно лемме 4, по которой либо [math]xy[/math], либо [math]xyx[/math] является бордером (в зависимости от четности длины строки).

[math]\triangleleft[/math]

Обратный морфизм

Определение:

Обратный морфизм [math]h^{-1}[/math] определяется как отображение: [math]xy \rightarrow x[/math], [math]x \rightarrow \left\{ \begin{array}{ll} y, \overline{xx}\\ x, \text{otherwise}\\ \end{array} \right. [/math] Здесь [math]\overline{xx}[/math] обозначает, что после этого вхождения [math]x[/math] в строке опять следует [math]x[/math].

Обратный морфизм позволяет из строки [math]f_n[/math] получить строку [math]f_{n-1}[/math].

Пример:

[math]f_4=xyxxy[/math].

Будем последовательно применять морфизм:

Префикс [math]xy[/math] переходит в [math]x[/math], центральный [math]x[/math] переходит в [math]y[/math], а суффикс [math]xy[/math] также переходит в [math]x[/math].

Получили [math]xyx = f_3[/math].

Связь с задачей о построении исключений

Утверждение (3):

Для любого целого [math]n \geqslant 7[/math] [math]f_n[/math] содержит куб некоторой подстроки.

[math]\triangleright[/math]

Строка [math]f_7 = xyxxyxyxxyxxyxyxxyxyx[/math] содержит подстроку [math]xyxxyxxyx = (xyx)^3 [/math] и является префиксом [math]f_n[/math] для [math]n \geqslant 7[/math].

[math]\triangleleft[/math]

Теорема (1):

Никакая строка [math]f_n[/math] не содержит подстроки кратности [math]4[/math].

Утверждение (4):

Бесконечная строка Фибоначчи [math]f_{\infty}[/math] является решением задачи построения [math](2,4)[/math]-исключения

[math]\triangleright[/math]

Это следует из утверждения и теоремы выше.

[math]\triangleleft[/math]

См. также

• Слово Туэ-Морса

Источники информации

• Билл Смит «Методы и алгоритмы вычислений на строках» — издательство «Вильямс» — 2006 — стр. 100-107