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.

closed as off-topic by Aryeh, Jan Johannsen, Emil Jeřábek, Hsien-Chih Chang 張顯之, D.W. Apr 9 '18 at 22:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Aryeh, Jan Johannsen, Emil Jeřábek, Hsien-Chih Chang 張顯之, D.W.
If this question can be reworded to fit the rules in the help center, please edit the question.


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.