enter image description here


I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I am back in q0 and the $ is removed from the stack I stop


2 Answers 2


There are several alternatives for the definition of a PDA, all of which are equivalent, in the sense that computationally they specify the same class of languages. To answer your question, you can perhaps take a look at the precise definition of PDAs you are working with.

For the following, with $X_\varepsilon$ I mean $X\cup\{\varepsilon\}$.

Some definitions use the signature $$\delta : Q\times\Sigma_\varepsilon\times\Gamma\to \mathcal{P}(Q\times\Gamma^*)$$ for the transition function, where $\Gamma$ is the stack alphabet. From this signature, it is evident that you need to have a symbol in the stack in order to move on. Of course, with this definition all PDAs are initialized with some initial symbol in the stack, before they start running. Otherwise, the PDA will never be able to make its first transition.

There are definitions, though, that use the signature $$\delta : Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon\to \mathcal{P}(Q\times\Gamma^*)$$ or $$\delta : Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon\to \mathcal{P}(Q\times\Gamma_\varepsilon)$$ The difference of the two last signatures is in the number of stack symbols they are allowed to push with each transition. But both definitions allow no symbol $(\varepsilon)$ to be popped from the stack. So with these signatures, moves are allowed under empty stacks and the PDA is usually initialized with an empty stack.

From the PDA in the picture, it looks like you are using one of the two latter definitions or something similar, where a PDA is allowed to pop nothing from the stack. So, when you arrive again in $q_0$ with an empty stack (because you removed the last symbol $(\$)$ in it) you are allowed to move to state $q_1$ by reading nothing from the input string, popping nothing from the stack and pushing again the dollar symbol.


A PDA (including a NPDA) can only move if there is a symbol on the top of the stack, the possible moves depend on the current state, the symbol on the top of the stack and the input symbol (or $\epsilon$). No stack, no further moves possible.

  • 1
    $\begingroup$ You can "move around" in a PDA with an empty stack, as long as you don't use transitions that p0p something from the stack. Perhaps at some point you will push something. Then you can pop. $\endgroup$
    – frabala
    Mar 28, 2020 at 10:08
  • $\begingroup$ @frabala no. A move considers top of stack symbol, every move. $\endgroup$
    – vonbrand
    Apr 5, 2020 at 0:36
  • $\begingroup$ I have posted an answer that also settles (my opinion regarding) our discussion. $\endgroup$
    – frabala
    Apr 5, 2020 at 8:51
  • $\begingroup$ As far as I know only the poor students taught from the Sipser book are allowed to move on empty stack. Shaking my head. $\endgroup$ May 5, 2020 at 13:20
  • $\begingroup$ I believe the Sipser book is (was?) widely used. The course notes (written by the professor) at my university also allow moves with an empty stack. $\endgroup$
    – frabala
    May 5, 2020 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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