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
