4
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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$? $\endgroup$ – Brian M. Scott May 8 '13 at 13:52
  • $\begingroup$ @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$. $\endgroup$ – J.-E. Pin Feb 1 '16 at 17:55
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You are right, I edited the answer to correct the mistake @MJD pointed out. $\endgroup$ – Gnattuha May 8 '13 at 14:59
  • 1
    $\begingroup$ I'm still missing something. Aren't $L_1$ and $L_2$ identical? $\endgroup$ – MJD May 8 '13 at 15:23
  • $\begingroup$ @MJD is right; I replaced union with concatenation. $\endgroup$ – Gnattuha May 8 '13 at 17:54
  • $\begingroup$ But if $L_1$ and $L_2$ are identical, why not just write $L_1L_1$? $\endgroup$ – MJD May 8 '13 at 18:01
  • 1
    $\begingroup$ @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. $\endgroup$ – xan May 8 '13 at 20:39

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.