# Is any formal language with given restriction context free?

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.

• 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 '16 at 17:55

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.
• I'm still missing something. Aren't $L_1$ and $L_2$ identical? – MJD May 8 '13 at 15:23
• 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