1
$\begingroup$

I'm trying to prove that that language isn't a context free:

$ L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$

I succeed to prove that $L = ww$ isn't context free, but not the language above. What am I doing wrong?

$\endgroup$
1
$\begingroup$

Here is the simplest way. Suppose that your language were context-free, and consider its intersection with $0^*(10)^*110^*(10)^*$. Applying further simple manipulations, you reach the language $\{a^nb^mc^nb^m : n,m \geq 0\}$, which is known not to be context-free.

If you insist on using the pumping lemma, perhaps you can get inspiration from this argument.

$\endgroup$
  • $\begingroup$ Not sure how this inspires arguments using the pumping lemma, but at least it proves the statement. $\endgroup$ – D. Ben Knoble May 18 at 18:07
  • $\begingroup$ It could suggest which word to pump. $\endgroup$ – Yuval Filmus May 18 at 18:08

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.