Why is the language $A=\{wtw^r: w,t\in\{0,1\}^*\text{ and }|w|=|t|\}$ not a context free language?
It is turning out to be really tricky. Is there an easy way to show this?
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ I tried pumping lemma but I think the problem is more tricky than I think. $\endgroup$– user39969Nov 12, 2015 at 20:32
-
1$\begingroup$ Were you trying to prove it's context free or trying to prove its not ? If you tried proving it is, how pumping lemma is of help ? $\endgroup$– advocateofnoneNov 12, 2015 at 20:38
-
1$\begingroup$ What have you tried? Have you tried the methods in our reference questions, e.g., cs.stackexchange.com/q/265/755 and cs.stackexchange.com/q/18524/755 and cs.stackexchange.com/q/33228/755? Have you searched carefully through other questions tagged context-free? We expect you to search carefully and exhaust all approaches you can think of before asking, and to show us in the question what you tried. $\endgroup$– D.W. ♦Nov 12, 2015 at 20:54
-
1$\begingroup$ What do you mean "work"? Work for what? If you're trying to apply the pumping lemma, don't just guess -- try to work out the details carefully, and then write it down in the question. This may require substantial work on your part, but you're asking for help from others, so we expect you to do whatever parts you can on your own. $\endgroup$– D.W. ♦Nov 12, 2015 at 20:55
-
1$\begingroup$ Without trying it, I'd at least say that you're on the right track. What's wrong with trying the simpler $0^p1^p0^p$? (Again, having not tried it--just off the top of my head.) $\endgroup$– Rick DeckerNov 12, 2015 at 20:56
|
Show 4 more comments