Определение
| Определение: |
Морфизмом называется отображение [math]h[/math], которое каждоый букве [math]\lambda[/math] из алфавита [math]A[/math] ставит в соответствие строку [math]h(\lambda)[/math] из множества [math]A^{+}[/math]. отображение [math]h[/math] также распространяется на любую строку [math]x[/math] из множества [math]A^{+}[/math] путем использования следующего тождества:
[math]h(x) = h(x[1])h(x[2])...h(x[n])[/math].
Для полноты распространим отбражение на множество [math]A^{*}[/math], положив, что для любого морфизма [math]h(\epsilon) = \epsilon[/math]. |
Любой морфизм [math]h[/math] можно применять к исходной строке [math]x_0[/math] любое число раз, тем самым генерируя последовательность итераций [math]h^{*}(x_0)[/math] по следующему правилу:
[math]h^{*}(x_0) = \{h^0(x_0), h^1(x_0),...\}[/math].
где [math]h^0(x_0) = x_0[/math] и для любого целого [math]k \geq 1 h^k(x_0) = h(h^{k-1}(x_0))[/math].
Например:
[math]A = \{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]h(a) = ab[/math]
- [math]h(b) = a[/math]
|
Свойства
Введем множество
Леммы
| Лемма: |
[math] \exists k : \forall n \geq k \Rightarrow F_{n}^2 [/math] - префикс [math]F_{n+2}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math] F_{n+2} = F_{n+1}F_{n} = F_{n}F_{n-1}F_{n} = F_{n}F_{n-1}F_{n-1}F_{n-2}[/math][math] = F_{n}F_{n-1}F_{n-2}F_{n-3}F_{n-2} = F_{n}F_{n}F_{n-3}F_{n-2}[/math]
Так как мы пользовались формулой [math]F_{n-1} = F_{n-2}F_{n-3}[/math], то рассуждения верны для [math]n \geq 4[/math]. Следовательно, [math]k \geq 6[/math] |
| [math]\triangleleft[/math] |
