# Is the language of words that contain a square regular or context-free?

A word is square-free if it contains no non-empty sub word of the form $$y^2$$. Your language consists of all words over $${a,b}$$ which are not square-free. It is not difficult to enumerate (using exhaustive search) all square-free words over $${a,b}$$:
$$epsilon, a, b, ab, ba, aba, bab.$$
Since this list is finite, the language of square-free words over $${a,b}$$ is trivially regular, and so is its complement.

In contrast, the language of square-free words over $${a,b,c}$$ is not regular. This follows from the existence of an infinite square-free word $$w$$, which can be obtained from the Thue–Morse sequence.

Indeed, I claim that the set of prefixes of $$w$$ is pairwise inequivalent modulo your language. To see this, let $$x,y$$ be two such prefixes, say $$x$$ is a prefix of $$y$$. Then $$y = xz$$, and so $$xz$$ is square-free while $$yz = xz^2$$ isn’t.

Alternatively, we can apply the pumping lemma to the language of all square-free words over $${a,b,c}$$. If the pumping length is $$n$$, take the prefix of $$w$$ of length $$n$$, and pump it up so that it contains a square. Similarly, since the Thue–Morse sequence is an infinite binary cube-free sequence, the language of cube-free words over $${a,b}$$ is not regular.

The latter argument shows that the language of square-free words over $${a,b,c}$$ and the language of cube-free words over $${a,b}$$ are not context-free. This leaves the following questions open:

1. Is the language of non-square-free words over $${a,b,c}$$ context-free?
2. Is the language of non-cube-free words over $${a,b}$$ context-free?