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.

| cite | improve this answer | |

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