2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ By pumping you can not only add $a$s, but also remove them. $\endgroup$ – Karolis Juodelė May 10 '13 at 10:18
  • $\begingroup$ This seems related to the $xyx$ problem, which did not get a decent answer. However, here the prefix and suffix can overlap. $\endgroup$ – Hendrik Jan May 10 '13 at 10:31
  • $\begingroup$ @KarolisJuodelė, right! I don't know why I forgot about that. This solves all problems, thanks! $\endgroup$ – xan May 10 '13 at 10:36
  • $\begingroup$ 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. $\endgroup$ – JeffE May 10 '13 at 15:12
  • $\begingroup$ @JeffE, I wouldn't too, but yes it does with given definition. $\endgroup$ – xan May 10 '13 at 17:53
1
$\begingroup$

Try to use closure properties instead.

Closer hint:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.