**Ex. from Shallit (nice!).**

Let be the class of context-free languages and be the class of regular languages. Let be the language of not-square words. Then .

**Proof.**

To prove that is not regular, it is sufficient to prove that is not regular, since the regular languages are closed under complement. Suppose is regular, then by the pumping lemma for regular languages there exists such that for every word with there exist satisfying s.t. for every . Now we consider the square . Then for any pumping decomposition s.t. , it must be . Then for some , hence is clearly not a square. This contradicts the pumping lemma so is not regular. Hence is not regular.

In order to prove that is context-free consider the following grammar:

We claim . Let be not-square.

For define .

Now we pose a condition on the parity of .

If for some , then for some s.t. . Consider the following production

.

Then .

Otherwise for some , then for some s.t. . Since is not a square, there exists the least s.t. . Now we write for

and

.

Then and . Hence , so and follows.

Now we claim and prove that . Let . Without loss of generality we assume the productions to be of the form , since otherwise is odd and therefore is not a square. Let w.l.o.g. to be . Let be the height of the parse sub-tree of starting from and let be the word parsed by the same tree, similarly let be the height of the parse sub-tree of starting from and be the word produced. It must be that .

Now let .

We claim that since imply .

Then .

This proves that is not a square. Hence . This proves .

**Q.E.D.**