Is $L$ always context free?

114 Views Asked by At

Consider the formal language $L$ over some finite alphabet $\Sigma$ consisting of all words over $\Sigma$ that have non-trivial period (non empty prefix that is also a suffix). Is $L$ always context free?

It is a modification of this question. I think it's much more difficult, because it's not possible (I think) to give a counter example. Maybe pumping lemma will do?

2

There are 2 best solutions below

0
On BEST ANSWER

Let $N$ be the pumping lemma's constant, and consider $\sigma = a^N b^N a^N b^N$. The $a$s are too far apart to be pumped together, same for the $b$s.

0
On

If by "non-trivial period" it is meant $L = \{w^k \colon w \in \Sigma^+ \text{ and } k \ge 2\}$, the same sort of argument works for $a^N b a^N b a^N b$: Can pump at most two stretches of $a$s, if pumping a piece including a $b$ it will be too short to replicate $a^N b$.