One can create a finite word from anything.
From Python objects:
{{{id=0| Word('abfasdfas') /// word: abfasdfas }}} {{{id=1| Word([2,3,4,5,6,6]) /// word: 234566 }}} {{{id=2| Word((0,1,2,1,2,)) /// word: 01212 }}}From an iterator:
{{{id=3| it = iter(range(10)) Word(it) /// word: 0123456789 }}}From a function:
{{{id=4| f = lambda n : (3 ^ n) % 5 Word(f, length=20) /// word: 13421342134213421342 }}}One can create an infinite word.
From an iterator:
{{{id=5| from itertools import count, repeat Word(count()) /// word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,... }}} {{{id=6| Word(repeat('a')) /// word: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... }}}From a function:
{{{id=7| f = lambda n : (3 ^ n) % 5 Word(f) /// word: 1342134213421342134213421342134213421342... }}}There are more than one hundreds methods and algorithms implemented for finite words and infinite words. One can list them using the TAB command:
{{{id=8| w = Word(range(10)) w.<TAB> /// }}}For instance, one can slice an infinite word to get a certain finite factor and compute its factor complexity:
{{{id=9| w = Word(p % 3 for p in primes(10000)) w /// word: 2021212122112122211211221212121221211122... }}} {{{id=10| factor = w[1000:2000] factor /// word: 1122111211211222121222211211121212211212... }}} {{{id=11| map(factor.number_of_factors, range(20)) /// [1, 2, 4, 8, 16, 32, 62, 110, 156, 190, 206, 214, 218, 217, 216, 215, 214, 213, 212, 211] }}}Creation of a word morphism:
from a dictionary:
{{{id=12| m = WordMorphism({'a':'abcab','b':'cb','c':'ab'}) print m /// WordMorphism: a->abcab, b->cb, c->ab }}}from a string:
{{{id=13| m = WordMorphism('a->abcab,b->cb,c->ab') print m /// WordMorphism: a->abcab, b->cb, c->ab }}}Image of a word under a morphism:
{{{id=14| m('a') /// word: abcab }}} {{{id=15| m('abcabc') /// word: abcabcbababcabcbab }}}Power of a morphism:
{{{id=16| print m ^ 2 /// WordMorphism: a->abcabcbababcabcb, b->abcb, c->abcabcb }}}Incidence matrix:
{{{id=17| matrix(m) /// [2 0 1][2 1 1][1 1 0] }}}Iterated image under a morphism:
{{{id=18| print m /// WordMorphism: a->abcab, b->cb, c->ab }}} {{{id=19| m('c') /// word: ab }}} {{{id=20| m(m('c')) /// word: abcabcb }}} {{{id=21| m(m(m('c'))) /// word: abcabcbababcabcbabcb }}} {{{id=22| m('c', 3) /// word: abcabcbababcabcbabcb }}}Infinite fixed point of morphism:
{{{id=23| m('a', Infinity) /// word: abcabcbababcabcbabcbabcabcbabcabcbababca... }}}or equivalently:
{{{id=24| m.fixed_point('a') /// word: abcabcbababcabcbabcbabcabcbabcabcbababca... }}}Let $w$ be a infinite word over an alphabet $A=A_0$.
$w\in A_0^*\xleftarrow{\sigma_0}A_1^*\xleftarrow{\sigma_1}A_2^*\xleftarrow{\sigma_2} A_3^*\xleftarrow{\sigma_3}\cdots$
A standard representation of $w$ is obtained from a sequence of substitutions $\sigma_k:A_{k+1}^*\to A_k^*$ and a sequence of letters $a_k\in A_k$ such that:
$w = \lim_{k\to\infty}\sigma_0\circ\sigma_1\circ\cdots\sigma_k(a_k)$.
Given a set of substitutions $S$, we say that the representation is $S$ -adic standard if the subtitutions are chosen in $S$.
Let $A_0=\{g,h\}$, $A_1=\{e,f\}$, $A_2=\{c,d\}$ and $A_3=\{a,b\}$. Let $\sigma_0 : \begin{array}{l}e\mapsto gh\\f\mapsto hg\end{array}$, $\sigma_1 : \begin{array}{l}c\mapsto ef\\d\mapsto e\end{array}$ and $\sigma_2 : \begin{array}{l}a\mapsto cd\\b\mapsto dc\end{array}$.
$\begin{array}{lclclcl} g \\ gh & \xleftarrow{\sigma_0} & e \\ ghhg & \xleftarrow{\sigma_0} & ef & \xleftarrow{\sigma_1} & c \\ ghhggh & \xleftarrow{\sigma_0} & efe & \xleftarrow{\sigma_1} & cd & \xleftarrow{\sigma_2} & a\end{array}$
Let's define three morphisms and compute the first nested succesive prefixes of the s-adic word:
{{{id=25| sigma0 = WordMorphism('e->gh,f->hg') sigma1 = WordMorphism('c->ef,d->e') sigma2 = WordMorphism('a->cd,b->dc') /// }}} {{{id=26| words.s_adic([sigma2],'a') /// word: cd }}} {{{id=27| words.s_adic([sigma1,sigma2],'ca') /// word: efe }}} {{{id=28| words.s_adic([sigma0,sigma1,sigma2],'eca') /// word: ghhggh }}}When the given sequence of morphism is finite, one may simply give the last letter, i.e. 'a', instead of giving all of them, i.e. 'eca':
{{{id=29| words.s_adic([sigma0,sigma1,sigma2],'a') /// word: ghhggh }}}But if the letters don't satisfy the hypothesis of the algorithm (nested prefixes), an error is raised:
{{{id=30| words.s_adic([sigma0,sigma1,sigma2],'ecb') /// Traceback (most recent call last): ValueError: The hypothesis of the algorithm used is not satisfied: the image of the 3-th letter (=b) under the 3-th morphism (=WordMorphism: a->cd, b->dc) should start with the 2-th letter (=c). }}}Let $A=A_i=\{a,b\}$ for all $i$ and Let $S = \left\{ tm : \begin{array}{l}a\mapsto ab\\b\mapsto ba\end{array}, fibo : \begin{array}{l}a\mapsto ab\\b\mapsto a\end{array} \right\}$.
$\begin{array}{lclclcl} a \\ ab & \xleftarrow{tm} & a \\ abba & \xleftarrow{tm} & ab & \xleftarrow{fibo} & a \\ abbaab & \xleftarrow{tm} & aba & \xleftarrow{fibo} & ab & \xleftarrow{tm} & a \end{array}$
Let's define the Thue-Morse and the Fibonacci morphism and let's import the repeat tool from the itertools:
{{{id=31| tm = WordMorphism('a->ab,b->ba') fib = WordMorphism('a->ab,b->a') from itertools import repeat /// }}}Fixed point are trivial examples of infinite s-adic words:
{{{id=32| words.s_adic(repeat(tm), repeat('a')) /// word: abbabaabbaababbabaababbaabbabaabbaababba... }}} {{{id=33| tm.fixed_point('a') /// word: abbabaabbaababbabaababbaabbabaabbaababba... }}}Let's alternate the application of the substitutions $tm$ and $fibo$ according to the Thue-Morse word:
{{{id=34| tmwordTF = words.ThueMorseWord('TF') words.s_adic(tmwordTF, repeat('a'), {'T':tm,'F':fib}) /// word: abbaababbaabbaabbaababbaababbaabbaababba... }}}Random infinite s-adic words:
{{{id=35| from sage.misc.prandom import randint def it(): while True: yield randint(0,1) words.s_adic(it(), repeat('a'), [tm,fib]) /// word: abbaabababbaababbaabbaababbaabababbaabba... }}} {{{id=36| words.s_adic(it(), repeat('a'), [tm,fib]) /// word: abbaababbaabbaababbaababbaabbaababbaabba... }}} {{{id=37| words.s_adic(it(), repeat('a'), [tm,fib]) /// word: abaaababaabaabaaababaabaaababaaababaabaa... }}}Soon in Sage...