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$
5
  • $\begingroup$ By pumping you can not only add $a$s, but also remove them. $\endgroup$ May 10, 2013 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$ May 10, 2013 at 10:31
  • $\begingroup$ @KarolisJuodelė, right! I don't know why I forgot about that. This solves all problems, thanks! $\endgroup$
    – xan
    May 10, 2013 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, 2013 at 15:12
  • $\begingroup$ @JeffE, I wouldn't too, but yes it does with given definition. $\endgroup$
    – xan
    May 10, 2013 at 17:53

1 Answer 1

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.