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 ??
$\begingroup$
$\endgroup$
3
-
$\begingroup$ If the question is "can a PDA transition simply replace the top element of the stack instead of removing it or adding something", then the answer is "yes". $\endgroup$– G. BachCommented Nov 6, 2013 at 17:00
-
$\begingroup$ @G. Bach Yep.. That's what i was looking for... Thanks... $\endgroup$– ShubhamCommented Nov 6, 2013 at 18:45
-
$\begingroup$ @Patrick87 make this to an answer? $\endgroup$– SubhayanCommented Nov 7, 2013 at 1:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
(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$.
