Is any formal language with given restriction context free?

138 Views Asked by At

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.

1

There are 1 best solutions below

7
On

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.