# Is $L$ always context free?

Consider formal language $L$ over finite alphabet $\Sigma$ consisting of all words over $\Sigma$ that have non-trivial period (non empty prefix that is also a suffix). Is $L$ always context free?

Maybe pumping lemma will do? I was advised to try with a word $a^Nb^Na^Nb^N$ but if I pump only second block of $a$ then this word still is in $L$, because it has non empty prefix $a^Nb^N$ that is also a suffix.

• By pumping you can not only add $a$s, but also remove them. – Karolis Juodelė May 10 '13 at 10:18
• This seems related to the $xyx$ problem, which did not get a decent answer. However, here the prefix and suffix can overlap. – Hendrik Jan May 10 '13 at 10:31
• @KarolisJuodelė, right! I don't know why I forgot about that. This solves all problems, thanks! – xan May 10 '13 at 10:36
• Does the word algebra have nontrivial period? It has a non-empty prefix (a) that is also a suffix, but I wouldn't call it periodic. – JeffE May 10 '13 at 15:12
• @JeffE, I wouldn't too, but yes it does with given definition. – xan May 10 '13 at 17:53

## 1 Answer

Try to use closure properties instead.

Closer hint:

CFL is closed against (pre)image of language homomorphisms and intersection with regular languages.