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.

Improve this question
$\endgroup$
5
  • $\begingroup$ By pumping you can not only add $a$s, but also remove them. $\endgroup$
    – Karolis Juodelė
    Commented 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$
    – Hendrik Jan
    Commented 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
    Commented 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
    Commented May 10, 2013 at 15:12
  • $\begingroup$ @JeffE, I wouldn't too, but yes it does with given definition. $\endgroup$
    – xan
    Commented May 10, 2013 at 17:53

1 Answer 1

Reset to default
1
$\begingroup$

Try to use closure properties instead.

Closer hint:

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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