Wprowadzimy kilka przykładów ciekawych abstrakcyjnych tekstów, skończonych i nieskończonych. Słowa te są definiowane za pomocą różnego typu operacji: morfizmów, rekurencji, poprzez jakiś wzór itp. Specjalne abstrakcyjne słowa są przedmiotem badań w kombinatoryce słów, ale również są użyteczne przy testowaniu algorytmów tekstowych, tak więc mają one znaczenie praktyczne pomimo ich abstrakcyjności. Poza tym słowa te mają bardzo ciekawe własności związane z różnymi problemami, dla których konstruuje się efektywne algorytmy.
Jeśli \(h : \Sigma \to \Sigma\) jest morfizmem takim, że \(h(a)\) zaczyna się od litery \(a\), to \(h^{\infty}(a)\) jest nieskończonym słowem, którego prefiksami są wszystkie słowa postaci \(h^n(a)\). Piszemy wtedy również \(h^{\infty}(a) = \lim_{n\ \to \infty}\;h^n(a)\).
Słowa tak generowane nazywamy morficznymi. Słowa te są z reguły również definiowane przez rekurencje. Typowymi słowami definiowanymi przez morfizmy i rekurencje są słowa Thue-Morse'a, słowa Fibonacciego i słowa Sturma.
Słowo nazywamy beznakładkowym (bez nakładki) gdy nie zawiera podsłowa postaci \(avava\), gdzie \(a\) jest niepuste. Słowo \(u\) nazywamy kwadratem gdy jest postaci \(u=xx\), dla pewnego niepustego \(x\).
Niech \(Fib_{\infty} = \lim_{n\to \infty}\;Fib_n\) będzie słowem nieskończonym Fibonacciego. Skończone słowa Fibonacciego to
Nieskończone słowa mające tę własność są nazywane słowami Sturma. Są to słowa o minimalnej gęstości podsłów, które nie są okresowe od pewnego miejsca. Zachodzi następujący fakt:
Jeśli dla pewnego \(k\) słowo nieskończone ma co najwyżej \(k\) róznych podsłów długości \(k\), to słowo to jest okresowe od pewnego miejsca.
Nieskończone słowo Thue-Morse'a, które pojawiło się w pracy matematycznej około 100 lat temu i służyło do dowodu tego, że jest nieskończenie wiele tekstów nie zawierających powtórzeń. Słowo to nie zawiera podsłowa postaci \(x^3\), gdzie \(x\) niepuste.
\(Thue_{\infty} = 011010011001011010010110 \ldots \) - nieskończone słowo Thue-Morse'a.
Podobnie definiujemy skończone słowa Thue-Morse'a:
Słowo \(Thue_{\infty}\) możemy również zdefiniować jako nieskończony ciąg binarny, na \(n\)-tym miejscu jest jedynka jeśli liczba jedynek w zapisie binarnym \(n\) jest nieparzysta (numerujemy pozycje od zera).
Słowo \(Thue_{\infty}\) możemy też zdefiniować za pomocą morfizmu: \(h(0)=01,\ h(1)=10\), wtedy \(Thue_{\infty}\ =\ h^{\infty}(a).\)
Najciekawszą własnością słów Thue-Morse'a jest ich beznakładkowość, oraz (w konsekwencji) fakt, że nie zawierają trzecich potęg niepustych słów. Słowa te zawierają kwadraty. Każdy kwadrat w słowie Thue-Morse'a ma rozmiar postaci \(2^k\) lub \(3\cdot 2^k\). Wiele własności tych słów wynika z następującego faktu:
Niech \(Occ(x,\, Thue_{\infty})\) będzie zbiorem początkowych pozycji wystąpień niepustego słowa \(x\) w słowie Thue-Morse'a, wtedy wszystkie elementy zbioru \(Occ(x,\, Thue_{\infty})\) są tej samej parzystości.
Definiujemy słowo bezkwadratowe \(M = 2102012\ldots\) w następujący sposób: kolejną literą jest liczba jedynek między kolejnymi zerami w słowie Thue-Morse'a. Słowo \(M\) nie zawiera podsłowa postaci \(x^2\), gdzie \(x\) niepuste.
Zastanówmy się jak bardzo słowo \(M\) różni się od słowa \(Thue_{\infty}\). Zmieńmy litery w słowie \(M\) zgodnie z następującym morfizmem: \(\mu(s) = (s+1)\ \bmod{3}\). Otrzymujemy ciąg \(\mu(M) = 0210120\ldots\).
Zdefiniujmy słowo \(\bar{B} = 01000101010 \ldots\) jako nieskończony ciąg binarny, w którym na \(n\)-tym miejscu jest jedynka jeśli rozmiar końcowego bloku jedynek w zapisie binarnym \(n\) jest nieparzysty (numerujemy pozycje od zera). Wtedy ciąg \(\mu(M)\) różni się od \(Thue_{\infty}\) dokładnie na tych pozycjach, gdzie \(\bar{B}\) zawiera jedynkę, w tych miejscach ciąg \(M\) zawiera zawsze dwójkę.
Dygresja: podobna konstrukcja w artykule ''Kwadraty'' w Delcie.
Inna konstrukcja tego samego słowa:
w ciągu Thue-Morse każde 00 zamieniamy na 20, każde 11 zamieniamy na 21.
Dygresja: podobna konstrukcja w artykule ''Kwadraty'' w Delcie.
Ciekawymi słowami są ciągi reprezentujące sekwencje ruchów w grze Wieże Hanoi.
\(H\) jest ciągiem ruchów w nieskończonej grze "Wieże Hanoi" (alfabet \( \Sigma = \lbrace \overleftarrow{a},\, \overleftarrow{b},\, \overleftarrow{c},\, a,\, b,\, c \rbrace\)).
W grze tej mamy przenieść \(n\) krążków z wieży o numerze \(i\) na wieżę o numerze \(j\). Wieże są ponumerowane 1, 2, 3.
Przez \(a\), \(b\), \(c\) oznaczmy ruchy przeniesienia górnego krążka z jednej wieży na drugą, odpowiednio \(1 \to 2\), \(2 \to 3\), \(3 \to 1\). A przez \( \overleftarrow{a},\, \overleftarrow{b},\, \overleftarrow{c}\) ruchy odwrotne. Niech \(Han(n,\, i,\, j)\) oznacza minimalny ciąg przenoszący \(n\) krążków z wieży \(i\) na wieżę \(j\). Zachodzi dla \(k\notin \{i,\, j\}\):
$$Han(n,\, i,\, j) = Han(n − 1,\, i,\, k) Han(1,\, i,\, j) Han(n − 1,\, k,\, j).$$
Oznaczmy \(H(n) = Han(n,\, 1,\, 3)\), gdy \(n\) parzyste oraz \(H(n) = Han(n,\, 1,\, 2)\), gdy \(n\) nieparzyste. Wtedy definiujemy \( H = \lim_{n\to \infty}\;H(n)\)
Ciąg \(H\) ma reprezentację poprzez morfizm jak również poprzez pewne rekurencje. W ciągu tym nie ma podsłowa będącego
kwadratem.
\(\bar{K} = 221121221221121122\ldots\) słowo Kolakoskiego, samogenerujące się słowo.
Słowo \(\bar{K}\) spełnia równanie \(r(\bar{K})=\bar{K}\), gdzie \(r(x)\) oznacza ciąg długości kolejnych bloków (maksymalnych spójnych fragmentów zawierających takie same litery), np. \(r(1133322) = 2\;3\;2\).
Niech \(g(k)\) będzie liczbą jedynek w zapisie binarnym liczby \(k\).
Przykład. \(g(21)=3\) gdyż \(21=[10101]_2\) ma 3 jedynki w zapisie binarnym.
Ciekawymi tekstami mającymi związek z tą funkcją są słowa binarne \(P_n\), gdzie \(P_n\) jest \(n\)-tym wierszem trójkąta Pascala modulo 2.
$$P_n(i) = {\left(\begin{array}{c}n\\i\end{array}\right)} \mod 2.$$
Można potraktować te słowa jako nieskończone (w prawo) dopisując dużo zer, wtedy
słowo \(P_0\ =\ x\ =\ 1000...\). Każde nastepne słowo powstaje z poprzeniego stując jednocześnie do
wszystkich pozycji \(i\) w słowie (potencjalnie) nieskończonym (poza pozycją pierwszą) $$x_i=(x_{i-1}+x_i) \ modulo \ 2$$
Mamy:
$$P_{0}=1, \
P_{1}=11,\
P_{2}=101,\
P_{3}=1111,\
P_{4}=10001,\
P_{5}=110011$$
Słowa \(P_n\) mają następującą ciekawą własność: liczba jedynek w \(P_n\) jest równa \(2^{g(n)}\).
Niech \(W(n)\) oznacza zbiór pozycji zawierających jedynkę w zapisie binarnym liczby \(n\). Zachodzi:
$$P_n(k) = 1 \Leftrightarrow W(k) \subseteq W(n)$$
Rozważmy nieskończony ciąg, który jest konkatenacją kolejnych liczb naturalnych zapisanych w systemie dzisiętnym (zero zapisujemy jako \(0\)). Zatem
$$W\ =\ 012345678910111213141516171819202122232425262728293031323334353637\ldots$$
Niech \(W_n\) oznacza prefiks tego ciągu długości \(n\). Słowa \(W_n\) mają następującą ciekawą własność: dla każdych dwóch niepustych słów tej samej długości \(x\), \(y\) zachodzi
$$\lim_{n \rightarrow \infty} \frac{|Occ(x,\, W_n)|}{|Occ(y,\,W_n)|} = 1.$$
Oznacza to, że w pewnym sensie ciąg \(W\) jest losowy.
Binarnym słowem de Bruijna rzędu \(k\) nazywamy każde słowo \(x\) długości \(2^k\), które zawiera każde słowo binarne długości \(k\) jako słowo cykliczne. Inaczej mówiąc, jeśli dopiszemy do \(x\) na końcu jego prefix długości \(k - 1\). to otrzymane słowo będzie zawierać każde słowo długości \(k\) w sensie klasycznego słowa liniowego. Oczywiście najkrótsze słowo liniowe zawierające każde słowo długości \(k\) musi mieć długość co najmniej \(2^k + k - 1\), czyli słowa de Bruijna realizują to minimum.
Dla każdego \(k\) istnieje wykładniczo dużo względem \(2^k\) słów de Bruijna rzędu \(k\). Dla \(k=1\) możemy wziąć słowo \(ab\), jako słowo de Bruijna, dla \(k=2\) słowem de Bruijna jest \(aabb\), natomiast \(aaababbb\) jest słowem de Bruijna rzędu 3. Zauważmy, że wszystkie te słowa są leksykograficznie pierwszymi słowami de Bruijna danego rzędu. W jednym z następnych rozdziałów podamy efektywne algorytmy generowania leksykograficznie pierwszych ciągów de Bruijna.
Mamy alfabet trzyliterowy \(\{a,b,c\}\). Konstruujemy słowo bezkwadratowe wypisująć kolejne litery. Bierzemy zawsze kolejną literę różną od poprzedniej. Daje to zawsze dwie możliwości wyboru.
Aby zdeterminować konstrukcję i uzyskać poprawny ciąg dodajmy warunek, że każda kolejna litera musi być różna od środkowej litery dotychczasowego słowa. Dokładniej, przy wyznaczaniu \(i\)-tej litery interesuje nas litera o indeksie \(\lfloor i/2 \rfloor\) przy czym litery słowa numerujemy od zera.
Jeżeli to kryterium wciąż dopuszcza dwie możliwości, to wybieramy tę spośród niezabronionych liter, która występuje wcześniej w alfabecie. W ten sposób otrzymujemy takie oto słowo:
$$abacbcabacabcbacb\ldots$$
Okazuje się, że dowolnie długie słowo wygenerowane w ten sposób jest bezkwadratowe.