How to find the length of $f^{n}(a)$ and $i^{th}$ digit for any n such that length of $f^{n}(a)$ is greater than $i$.

102 Views Asked by At

Suppose $S$ is a finite set of characters, which we will assume is a subset of{a,b,c,d,e,f}. Then $S^*$ denotes the set of all sequences whose elements are these characters, that is, it is just the set of all strings, also called words, containing only the given set of characters. A morphism $f$ is a function $f: S → S^*$ that assigns to each character $x∈S$ some word $f(x)∈S^*$. The morphism $f$ can be extended to all words in $S^∗$ by defining $f(λ) =λ$ and $f(w·x) =f(w)·f(x)$, for all words $w∈S^*$ and characters $x∈S$. Here $λ$ is the empty word and $(·)$ denotes concatenation. Suppose $f(a)$ also has $a$ as the first character. Then consider the sequence of words $a,f(a),...,fn(a),...,$ where $f^0(a) = a $ and $f^n(a)=f(f^{n−1}(a))$. It can be seen that $f^{n−1}(a)$ is a prefix of $f^n(a)$ for all $n≥1$, and as $n→∞$ this sequence approaches a fixed, possibly infinite, word called its limit.

How to find the length of $f^{n}(a)$ and $i^{th}$ digit for any n such that length of $f^{n}(a)$ is greater than $i$.

1

There are 1 best solutions below

9
On

I will let $S=\{a,b,c\}$. You can make a matrix that shows what characters each character becomes. Each word corresponds to a column vector that shows the number of $a$s in the first entry, $b$s in the second and $c$s in the third. The matrix will take the character counts of a word $w$ and give the character counts of $f(w)$. The length of a word is then the sum of the entries in the column vector. The columns correspond to the input characters and each row is the number of a given output character generated by each input character.

As an example, let $f(a)=ab, f(b)=bcca, f(c)=cbc$ Then the matrix is $$\begin {bmatrix} 1&1&0\\1&1&1\\0&2&2 \end {bmatrix}$$ where the first column tells us that each $a$ in a word becomes one $a$ and one $b$ (in some order-we are not keeping track of that). Your starting word has the vector $$\begin {bmatrix} 1\\0\\0 \end {bmatrix}$$ and each application of $f$ corresponds on one multiplication by the matrix. To get the length of the $n^{th}$ iterate of $f$, multiply your starting vector by the $n^{th}$ power of the matrix and sum the components.

You can get an asymptotic growth rate for the length by finding the eigenvalues of the matrix and taking the largest. In the example, the largest eigenvalue is about $3.17$ corresponding to the eigenvector $\begin {bmatrix} 0.270\\0.585\\1 \end {bmatrix}$ The length will multiply by about $3.17$ each iteration and the proportion of letters will be as shown in the eigenvector.

For my example, $f(a)=ab, f^2(a)=abbcca, f^3(a)=abbccabccacbccbcab$ and so on.