Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Thoughts
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
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.
