Square-free word

In combinatorics, a square-free word is a word (a sequence of characters) that does not contain any subword twice in a row.

Thus a square-free word is one that avoids the pattern XX.

Over a two-letter alphabet {a, b} the only square-free words are the empty word and a, b, ab, ba, aba, and bab. However, there exist infinite square-free words in any alphabet with three or more symbols, as proved by Axel Thue.

One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence. That is, from the Thue–Morse sequence

one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is

Another example found by John Leech is defined recursively over the alphabet {a, b, c}. Let ${\displaystyle w_{1}}$ be any word starting with the letter a. Define the words ${\displaystyle \{w_{i}\mid i\in \mathbb {N} \}}$ recursively as follows: the word ${\displaystyle w_{i+1}}$ is obtained from ${\displaystyle w_{i}}$ by replacing each a in ${\displaystyle w_{i}}$ with abcbacbcabcba, each b with bcacbacabcacb, and each c with cabacbabcabac. It is possible to check that the sequence converges to the infinite square-free word

...
Wikipedia