I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive.

How I attempted it is by popping every 2 'a' for 1 'b' and then popping 1 'b' for 2 'c'. I don't understand why is this wrong.

I feel I am be overlooking something really minuscule.

  • $\begingroup$ Your language isn't context-free. $\endgroup$ – Yuval Filmus Nov 2 '20 at 12:40
  • $\begingroup$ @YuvalFilmus Ik, however what is wrong with my PDA. $\endgroup$ – Atom Nov 2 '20 at 12:40
  • $\begingroup$ Does this answer your question? cs.stackexchange.com/questions/8989/… $\endgroup$ – Yuval Filmus Nov 2 '20 at 12:41
  • $\begingroup$ No, the bounds of ‘n’ are different $\endgroup$ – Atom Nov 2 '20 at 12:42
  • $\begingroup$ There is not much difference between $n \geq 0$ and $n \geq 1$. Try to read past that. $\endgroup$ – Yuval Filmus Nov 2 '20 at 12:47

Yes you missed something ,

Lets review how your PDA works :

  1. we push a for each a we read
  2. we pop 2as for each b we read , then when stack is empty we push b for each b we read
  3. we pop b for each 2cs we read

Your PDA will accept strings of form a2nbn+mc2m

for ex , a4b5c6 , here n = 2 , m = 3

You push 4 as , then for each 2as you pop b , you pop 2bs , and 3 bs remain which are pushed to stack !!!

Hopefully you can see the problem here , no one told you that you are half way bs when you finished popping as

You continue , for each of the 6 cs you pop a b then you accept

You expect the string in the form a2nbn+mc2m , you compare a2nbn then bmc2m , of course if n = m you are correct , but there is no way to ensure this

  • $\begingroup$ Thank you so much, this is exactly the answer I was looking for! $\endgroup$ – Atom Nov 17 '20 at 2:34

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.