Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider formal language $L$ in which each word has non-trivial period (non empty prefix that is also a suffix) over finite alphabet. Is $L$ context free?

I think that $L$ can be non context free. I want to use pumping lemma for context free languages but I can't find a word that I can pump.

share|improve this question
2  
Are you sure that you mean what you wrote? The word $aabaa$ has a non-empty prefix that is also a suffix, but it’s not normally considered periodic at all. Are you sure that you don’t mean that every word has the form $u^n$ for some non-empty $u$ and some $n>1$? –  Brian M. Scott May 8 '13 at 13:52

1 Answer 1

Proving it by providing counter example should be easier than to the usage of pumping lemma.

The following language seems to satisfy non-trivial periodicity condition, but is not a context free.

Let $L=\{ a^i b^jc^k | \ i\geq j \geq k > 0 \}$, (known to be non-context free) , then $L L$ has non-trivial period ($a$) which is both prefix and suffix, but is not context-free.

share|improve this answer
    
You are right, I edited the answer to correct the mistake @MJD pointed out. –  Gnattuha May 8 '13 at 14:59
1  
I'm still missing something. Aren't $L_1$ and $L_2$ identical? –  MJD May 8 '13 at 15:23
    
@MJD is right; I replaced union with concatenation. –  Gnattuha May 8 '13 at 17:54
    
But if $L_1$ and $L_2$ are identical, why not just write $L_1L_1$? –  MJD May 8 '13 at 18:01
1  
@Gnattuha, the way I see it: $LL=\left\{a^ib^jc^ka^lb^mc^n: i\ge j\ge k>0 \wedge l\ge m\ge n>0\right\}$. Especially $a^3b^2ca^4b^4c^4$ and I don't see where it has non empty prefix that is also a suffix. –  xan May 8 '13 at 20:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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