-1
$\begingroup$

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.
$\endgroup$

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.

1
$\begingroup$

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.

$\endgroup$

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