46
правок
Изменения
м
Нет описания правки
==Определение==
{{Определение
|definition=Строками Фибоначчи называются строкиМорфизмом называется отображение <tex>h</tex>, удовлетворяющие следующим условиям:* которое каждоый букве <tex>F_0 = \epsilonlambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(пустая строка\lambda)* </tex> из множества <tex>A^{+}</tex>. отображение <tex>h</tex> также распространяется на любую строку <tex>F_1 = bx</tex>* из множества <tex>F_2 = aA^{+}</tex> путем использования следующего тождества:<br>* <tex>F_n h(x) = F_{n-h(x[1}F_{])h(x[2])...h(x[n-2}])</tex> (т.е. конкатенации строк <br>Для полноты распространим отбражение на множество <tex>F_A^{n-1*}</tex> и , положив, что для любого морфизма <tex>F_{n-2}h(\epsilon) = \epsilon</tex>).
}}
Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>x_0</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(x_0)</tex> по следующему правилу: <br>
<tex>h^{*}(x_0) = \{h^0(x_0), h^1(x_0),...\}</tex>. <br>
где <tex>h^0(x_0) = x_0</tex> и для любого целого <tex>k \geq 1 h^k(x_0) = h(h^{k-1}(x_0))</tex>. <br>
Например:<br>
<tex>A = \{a,b\}, h(a) = a, h(b) = ab</tex>. <br>
<tex>h^*(a) = \{a,a,...\}</tex> <br>
<tex>h^*(b) = \{b, ab, a^2b,..., a^kb...\}</tex><br>
{{Определение
|definition=Строки Фибоначчи - строки, порожденные следующим морфизмом:
* <tex>h(a) = ab</tex>
* <tex>h(b) = a</tex>
}}
==Свойства==
Введем множество
==Леммы==
{{Лемма
