[Solved]: Can we push and pop both at a single transition in a PDA?

Problem Detail: 

Let say I have a pda :

δ(q1,a,Z)=(q2,aZ)

δ(q2,a,aZ)=(q2,bZ)

Is this allowed....

you can see that in δ(q2,a,aZ)=(q2,bZ), we are basically popping 'a' and pushing 'b' for a single transition...

Is this allowed for PDA ??

Asked By : Shubham

Answered By : Patrick87

(Previously a comment)

Depends on how you define PDAs. The definition I consider canonical certainly does allow you to exactly this: it is assumed that each transition pops the top-most symbol, and pushes an arbitrary string. To represent not changing the stack, you'd push the same symbol you just popped; to pop one symbol, you'd push the empty string; to put $w$ on top of the stack, you'd push $wa$ (where $a$ is the top-most symbol); and to replace $a$ with $b$, you'd push $b$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16774