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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Строками Фибоначчи (англ. 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(b)[/math].


Примеры

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

  • [math]f_0 = b[/math]
  • [math]f_1 = a[/math]
  • [math]f_2 = ab[/math]
  • [math]f_3 = aba[/math]
  • [math]f_4 = abaab[/math]
  • [math]f_5 = abaababa[/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=ab=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)) = 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]f_n(x,y)[/math] не может содержаться подстроки [math]x^3[/math] или [math]y^2[/math].
Утверждение (2):
Для любого [math]n[/math] [math]f_nf_{n+1} \neq f_{n+1}f_n[/math].
[math]\triangleright[/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\,\,mod \,\,2)[/math].

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

Определение:
Обратный морфизм [math]h^{-1}[/math] определяется как отображение:
  • [math]ab \rightarrow a[/math],
  • [math]a \rightarrow a [/math] (если после [math]a[/math] следует [math]b[/math]) или [math] a \rightarrow b[/math] (в противном случае).

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