CLR cover

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]
  1. 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}^*$).
  2. If $|w|$ is a power of 3 then ${h}^{|w|}(w)\,=\, w\,w$.


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