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

Question

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.

Answer 1

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 a²ⁿb^n+mc^2m

for ex , a⁴b⁵c⁶ , 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 a²ⁿb^n+mc^2m , you compare a²ⁿbⁿ then b^mc^2m , of course if n = m you are correct , but there is no way to ensure this