# {a^n b^n c^n | n>=1} - PDA

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.

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

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