129
правок
Изменения
Нет описания правки
|proof= <tex>f_n(x,y) = h^n(y) = h^{n-k}(h^k(y))</tex>
<tex>f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y)) </tex> Так как <tex>h^k(x)=h^{k+1}(y)</tex>, то <tex>f_{n-k}(h^k(x),h^k(y)) = f_{n-k}(h^{k+1}(y),h^k(y))</tex>.
}}
'''Например''':
|statement= Для любого целого <tex>n \geqslant 3</tex> строка <tex>f_n</tex> имеет [[Основные_определения,_связанные_со_строками#border|бордеры]] <tex>f_i</tex> для <tex>i = n-2, n-4,\ldots,2-(n\,\,mod \,\,2)</tex>.
|proof=
Будем последовательно применять лемму 1
<tex>f_n=f_{n-1}f_{n-2}=f_{n-2}f_{n-3}f_{n-2}</tex>. Таким образом, <tex>f_{n-2}</tex> является бордером
Далее, <tex>f_n=f_{n-3}f_{n-3}f_{n-3}f_{n-4}=f_{n-4}f_{n-5}\ldots f_{n-4} </tex>. Получили, что <tex>f_{n-4}</tex> является бордером
Продолжая выполнять это преобразование, докажем лемму для всех заданных <tex>i</tex>
}}
{{Утверждение
|proof = Докажем для <tex>x^3</tex> методом математической индукции по <tex>f_n</tex>
База:
*:<tex>f_0=y,f_1=x</tex> {---} не содержат <tex>x^3</tex>
Переход:
*:Пусть <tex>n \geqslant 2</tex>, тогда <tex>f_n = f_{n-1}f_{n-2}</tex>
* <tex>a \rightarrow
\left\{ \begin{array}{ll}
\end{array}
\right. </tex>
}}
Обратный морфизм позволяет из строки <tex>f_n</tex> получить строку <tex>f_{n-1}</tex>.
'''Пример''':
*: <tex>f_4=xyxxy</tex>.
*: Будем последовательно применять морфизм:
*: Префикс <tex>xy</tex> переходит в <tex>x</tex>, центральный <tex>x</tex> переходит в <tex>y</tex>, а суффикс <tex>xy</tex> также переходит в <tex>x</tex>.
*: Получили <tex>xyx = f_3</tex>.
== Связь с задачей о построении исключений==
{{Утверждение
