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?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ Can you show in the question how you proved that $\{ww | w\in \Sigma^*\}$ isn't context-free? $\endgroup$– John L.Commented May 18, 2019 at 17:02
-
$\begingroup$ Possible duplicate of How to prove that a language is not context-free? $\endgroup$– David RicherbyCommented May 25, 2019 at 13:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered May 18, 2019 at 18:02
-
$\begingroup$ Not sure how this inspires arguments using the pumping lemma, but at least it proves the statement. $\endgroup$ Commented May 18, 2019 at 18:07
-
$\begingroup$ It could suggest which word to pump. $\endgroup$ Commented May 18, 2019 at 18:08