1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I tried pumping lemma but I think the problem is more tricky than I think. $\endgroup$ – user39969 Nov 12 '15 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$ – sashas Nov 12 '15 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 '15 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 '15 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 Decker Nov 12 '15 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy