0
$\begingroup$

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.

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

1 Answer 1

0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.