Материал из Викиконспекты
Определение
| Определение: |
| Морфизмом называется отображение [math]h : \Sigma^* \rightarrow \Sigma^*[/math], которое каждой букве [math]\lambda[/math] из алфавита [math]\Sigma[/math] ставит в соответствие строку [math]h(\lambda)[/math] из множества [math]\Sigma^{+}[/math],
затем данное отображение распространяется на [math]\Sigma^*[/math] следующим образом:
[math]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. [/math] |
Любой морфизм [math]h[/math] можно применять к исходной строке [math]s[/math] любое число раз, тем самым генерируя последовательность итераций [math]h^{*}(s)[/math] по следующему правилу:
[math]h^{*}(s) = \{h^0(s), h^1(s),...\}[/math].
где [math]h^0(s) = s[/math] и для любого целого [math]k \geq 1 :[/math] [math] h^k(s) = h(h^{k-1}(s))[/math].
Например:
- [math]\Sigma = \{a,b\}, h(a) = a, h(b) = ab[/math].
- [math]h^*(a) = \{a,a,...\}[/math]
- [math]h^*(b) = \{b, ab, a^2b,..., a^kb...\}[/math]
| Определение: |
Строками Фибоначчи являются строки над алфавитом [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 \geq 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] |
Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
См. такжеИсточники
- Билл Смит. Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус.)
