Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} $

Example 1

When the process is applied to the initial word $x=\sa{1221}$, it produces a list of ternary words starting with $\begin{array}{lcccccccccccccc} h^0(x) &=& \sa{1}&\sa{2}&\sa{2}&\sa{1}\\ h^1(x) &=& \sa{1}&\sa{0}&\sa{1}&\sa{0}&\sa{1}\\ h^2(x) &=& \sa{1}&\sa{1}&\sa{1}&\sa{1}&\sa{1}&\sa{1}\\ h^3(x) &=& \sa{1}&\sa{2}&\sa{2}&\sa{2}&\sa{2}&\sa{2}&\sa{1}\\ h^4(x) &=& \sa{1}&\sa{0}&\sa{1}&\sa{1}&\sa{1}&\sa{1}&\sa{0}&\sa{1}\\ h^5(x) &=& \sa{1}&\sa{1}&\sa{1}&\sa{2}&\sa{2}&\sa{2}&\sa{1}&\sa{1}&\sa{1}\\ h^6(x) &=& \sa{1}&\sa{2}&\sa{2}&\sa{0}&\sa{1}&\sa{1}&\sa{0}&\sa{2}&\sa{2}&\sa{1}\\ h^7(x) &=& \sa{1}&\sa{0}&\sa{1}&\sa{2}&\sa{1}&\sa{2}&\sa{1}&\sa{2}&\sa{1}&\sa{0}&\sa{1}\\ h^8(x) &=& \sa{1}&\sa{1}&\sa{1}&\sa{0}&\sa{0}&\sa{0}&\sa{0}&\sa{0}&\sa{0}&\sa{1}&\sa{1}&\sa{1}\\ h^9(x) &=& \sa{1}&\sa{2}&\sa{2}&\sa{1}&\sa{0}&\sa{0}&\sa{0}&\sa{0}&\sa{0}&\sa{1}&\sa{2}&\sa{2}&\sa{1}\\ \end{array}$

In particular, ${h}^9(x)=x\cdot\sa{00000}\cdot x$, which shows that the word $x$ has been reproduced.

Example 2

Applied to $y=\sa{121}$, the associated list starts with $\begin{array}{lcccccccccccccc} h^0(y) &=& \sa{1}&\sa{2}&\sa{1}\\ h^1(y) &=& \sa{1}&\sa{0}&\sa{0}&\sa{1}\\ h^2(y) &=& \sa{1}&\sa{1}&\sa{0}&\sa{1}&\sa{1}\\ h^3(y) &=& \sa{1}&\sa{2}&\sa{1}&\sa{1}&\sa{2}&\sa{1}\\ \end{array}$

Problem 109: Self-Reproducing Words

Word morphisms are frequently used to produce finite or infinite words because they are defined by the images of single letters. In the problem we consider another type of function that may be regarded as context dependent and is a kind of sequential transducer.

The working alphabet is $A=\{\sa{0},\sa{1},\sa{2}\}$. The image by $h$ of a word $w\in A^+$ is the word $${h}(w) = (\sa{0}\oplus a[0])\,(a[0]\oplus a[1])\,(a[1]\oplus a[2]) \cdots (a[n-1]\oplus \sa{0}),$$ where $\oplus$ is the addition modulo 3. Iterating $h$ from an initial word of $A^+$ produces longer words that have very special properties, as shown with the two examples.

Show that for any word $w\in A^+$ the two properties hold:\\[1mm]

There is an integer $m$ for which ${h}^m(w)$ consists of two copies of $w$ separated by a factor of zeros (i.e. a factor in $\sa{0}^*$).
If $|w|$ is a power of 3 then ${h}^{|w|}(w)\,=\, w\,w$.

References

S. Amoroso and G. Cooper. Tessellation structures for reproduction of arbitrary patterns. J. Comput. Syst. Sci., 5(5):455-464, 1971.

125 Problems in Text Algorithms

Example

Example 1

Example 2

Problem 109: Self-Reproducing Words

References