46
правок
Изменения
Нет описания правки
==Определение==
{{Определение
|definition='''Морфизмом ''' называется отображение <tex>h</tex>, которое каждоый букве <tex>\lambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>A^{+}</tex>. отображение }}Отображение <tex>h</tex> также распространяется на любую строку <tex>x</tex> из множества <tex>A^{+}</tex> путем использования следующего тождества:<br>
<tex>h(x) = h(x[1])h(x[2])...h(x[n])</tex>.<br>
Для полноты распространим отбражение на множество <tex>A^{*}</tex>, положив, что для любого морфизма <tex>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 </tex> <tex> 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>
{{Определение
|definition=Строки '''Строками Фибоначчи - ''' являются строки, порожденные следующим морфизмом:* <tex>A = \{a,b\}</tex>
* <tex>h(a) = ab</tex>
* <tex>h(b) = a</tex>
Также нетрудно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
== Литература ==
* ''Билл Смит'' '''Методы и алгоритмы вычислений на строках'''
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Слово Фибоначчи]]
