Can we put more than one element in stack at a time. Actually I am asking that this transition function is valid for PDA: ∆(q,a,z)=(q',aaz) Where:

  1. q and q' are states
  2. a is input symbol
  3. z is starting stack symbol
  4. This transition function is doing that if PDA is in q state and read input a and top element of stack is z then it goes to state q' and put aa in stack. Is above transition. Function is valid for PDA. And my college teacher said that it is true but I have never read this in any book that it is true neither I have read this is false.

It's not part of the normal definition of PDA, but it is an "equivalent" definition: If we say a PDA is something that can only push one symbol at a time, let's call yours a "Push-multiple-down Automata" , or PMDA. :)

Then you can show than any PDA is also a PMDA (that part is trivial), and that any PMDA can be turned into an equivalent PDA. The conversion consists of adding states for "pushing down a few at a time". So for instance, if I at some point should push the string "adbd", then I add in 3 extra states $s_1 \dots s_3$. I start by pushing "a" and transitioning to $s_1$, then from $s_1$ I push "d" and transition to $s_2$, and so on; and after pushing from $s_3$ I end up and the end state that the PMDA would have transitioned to in a single step.

Thus, pushing multiple symbols might be convenient in some descriptions, but doesn't alter the power of the machine. This is why it's usually not discussed.


Not the answer you're looking for? Browse other questions tagged or ask your own question.