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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
@brian-m-scott I suppose that the OP follows the definition of Lothaire, Combinatorics on words (see also the (French) entry Mot on wikipedia). A period of a word $a_1 \cdots a_n$ is a positive integer $p$ such that $1 \leqslant p \leqslant n$ and $a_{i+p} = a_i$ for $1 \leqslant i \leqslant n-p$. For instance $aabaa$ has periods $3$, $4$ and $5$. – J.-E. Pin Feb 1 at 17:55

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|cite|improve this answer
You are right, I edited the answer to correct the mistake @MJD pointed out. – Gnattuha May 8 '13 at 14:59
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
@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


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.