46
правок
Изменения
Нет описания правки
Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
==Обощенная строка Фибоначчи==
Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов <tex>a</tex> и <tex>b</tex> будем оперировать двумя произвольными строками <tex>x,y \in \Sigma^*</tex>:
*<tex>h(x) = xy</tex>
*<tex>h(y) = x</tex>
Таким образом "старый" морфизм будет частным случаем "нового" морфизма при <tex>x = a</tex> и <tex>y = b</tex>.
По аналогии можно вычислить <tex>h^*(y) = \{y, x, xy, xyx, \dots\}</tex>, и ,наконец, определить n-ую обобщенную строку Фибоначчи как:
{{Определение
|definition=Обобщенная строка Фибоначчи имеет вид <tex>f_n(x,y) = h^n(y)</tex>
}}
Первые несколько обобщенных строк имеют вид:
*<tex>f_0(x,y) = y</tex>
*<tex>f_1(x,y) = x</tex>
*<tex>f_2(x,y)= xy</tex>
*<tex>f_3(x,y)= xyx</tex>
*<tex>f_4(x,y) = xyxxy</tex>
А также в общем случае:
*<tex>f_n(x,y) = f_{n-1}(x,y)f_{n-2}(x,y)</tex>
{{Определение
|definition=Определим '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' как строку, содержащую все строки <tex>f_n(x,y), n \geq 0</tex> в качестве префиксов
}}
Поскольку <tex>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 = f_{n-k}(f_{k+1},f_k)</tex>.
'''Например''':
<tex>f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)</tex>
Это равенство походит также и для <tex>f_{\infty}: f_{\infty} = f_{\infty}(f_{n+1},f_{n}) = f_{n+1}f_n f_{n+1} f_{n+1} f_n f_{n+1} f_n f_{n+1} \dots</tex>
{{Утверждение
|statement=Бесконечная строка Фибоначчи <tex>f_{\infty}</tex> является решением задачи построения (2,4)-исключения
}}
Напомним, что в задаче построения <tex>(\alpha , r)</tex>-исключений требуется построить бесконечную строковую последовательность на алфавите размером <tex>\alpha</tex>, свободную от кратных подстрок порядка <tex>r</tex>, но содержащую кратные подстроки порядов <tex>2,3,\dots, r - 1</tex>.
<!--
