Слово Фибоначчи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники и см. также)
(Удалены лишние пункты)
Строка 1: Строка 1:
 +
<!---
 
==Определение==
 
==Определение==
 
{{Определение
 
{{Определение
Строка 25: Строка 26:
 
*<tex>h^*(b) = \{b, ab, a^2b,..., a^kb...\}</tex>
 
*<tex>h^*(b) = \{b, ab, a^2b,..., a^kb...\}</tex>
  
 
+
--->
 
{{Определение
 
{{Определение
 
|definition='''Строками Фибоначчи''' (англ. ''Fibostring'') являются строки над алфавитом <tex>\Sigma = \{a, b\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:
 
|definition='''Строками Фибоначчи''' (англ. ''Fibostring'') являются строки над алфавитом <tex>\Sigma = \{a, b\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:
Строка 89: Строка 90:
 
Это равенство походит также и для <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} \dots</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} \dots</tex>
 
{{Утверждение
 
{{Утверждение
|statement=Бесконечная строка Фибоначчи <tex>f_{\infty}</tex> является решением задачи построения (2,4)-исключения
+
|statement=Бесконечная строка Фибоначчи <tex>f_{\infty}</tex> является решением {{Acronym | задачи построения (2,4)-исключения| Требуется построить бесконечную строковую последовательность на алфавите размером 2, свободную от кратных подстрок порядка 4, но содержащую кратные подстроки порядков 2 и 3 }}
 
}}
 
}}
Напомним, что в задаче построения <tex>(\alpha , r)</tex>-исключений требуется построить бесконечную строковую последовательность на алфавите размером <tex>\alpha</tex>, свободную от кратных подстрок порядка <tex>r</tex>, но содержащую кратные подстроки порядов <tex>2,3,\dots, r - 1</tex>.
+
<!-- >.
 +
-->
  
 
<!--
 
<!--

Версия 15:41, 6 июня 2016


Определение:
Строками Фибоначчи (англ. Fibostring) являются строки над алфавитом [math]\Sigma = \{a, b\}[/math], полученные последовательным применением морфизма [math]h[/math]:
  • [math]h(a) = ab[/math]
  • [math]h(b) = a[/math]
к строке [math]s = b[/math], т.е. [math]h^*(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]

Лемма

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

Доказательство нетрудно получить методом математической индукции.

База: При [math]n = 2[/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]. Так как отображение h — линейно (т.е. [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](\alpha, r)[/math]-исключений

Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов [math]a[/math] и [math]b[/math] будем оперировать двумя произвольными строками [math]x,y \in \Sigma^*[/math]:

  • [math]h(x) = xy[/math]
  • [math]h(y) = x[/math]

Таким образом "старый" морфизм будет частным случаем "нового" морфизма при [math]x = a[/math] и [math]y = b[/math].

По аналогии можно вычислить [math]h^*(y) = \{y, x, xy, xyx, \dots\}[/math], и ,наконец, определить n-ую обобщенную строку Фибоначчи как:

Определение:
Обобщенная строка Фибоначчи (англ. generalized Fibostring) имеет вид [math]f_n(x,y) = h^n(y)[/math]


Первые несколько обобщенных строк имеют вид:

  • [math]f_0(x,y) = y[/math]
  • [math]f_1(x,y) = x[/math]
  • [math]f_2(x,y)= xy[/math]
  • [math]f_3(x,y)= xyx[/math]
  • [math]f_4(x,y) = xyxxy[/math]

А также в общем случае:

  • [math]f_n(x,y) = f_{n-1}(x,y)f_{n-2}(x,y)[/math]


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


Поскольку [math]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 = f_{n-k}(f_{k+1},f_k)[/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} \dots[/math]

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

См. также

Источники

  • Билл Смит. Методы и алгоритмы вычислений на строках. — стр. 100-107