Изменения
Нет описания правки
==Определение==
{{Определение
|definition='''Морфизмом''' называется отображение <tex>h</tex>, которое каждоый каждой букве <tex>\lambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>A^{+}</tex>, а каждой строке <tex>x</tex> из <tex>A^+</tex> ставит в соответсвие строку из <tex>A^+</tex> по следующему правилу :<tex>h(x) = h(x[1])h(x[2])...h(x[n])</tex> , где <tex>x[1], x[2], \dots, x[n]</tex> уже являются элементами <tex>A</tex>.
}}
Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>x_0</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(x_0)</tex> по следующему правилу: <br>
* <tex>f_5 = abaababa</tex>
==ЛеммыЛемма==
{{Лемма
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1} + f_{n-2}, n \geq 2</tex>.
|proof=
Доказательство нетрудно получить методом математической индукции.
База. При <tex>n = 2</tex> равенство очевидно.
Переход. Пусть <tex>f_n = f_{n-1} + f_{n-2}</tex>. <tex>f_{n+1} = h(f_n) = h(f_{n-1} + f_{n-2})</tex>. Т.к. h {{---}} линейна (т.е. <tex>h(x+yxy) = h(x) + h(y)</tex>), то можно продолжить равенство.<tex>f_{n+1} = h(f_{n-1}) + h(f_{n-2}) = f_{n} + f_{n-1}</tex>
}}
