Do NPDA work in parallel?

Question

Assume my language is $$ L= ww^{r}\ $$

Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice here. Now each branch will get the current stack contents and start its operation.

So my question is, do these branches operate in parallel or one after another? We have only one stack and each branch will do push/pop according to its requirement and changes the stack. Even if a branch results in dead end, we need to proceed further. How is a single stack able to manage this scenario, as stack contents are changed by each branch?

Answer 1

The difference between DPDA and NPDA is that in NPDA there may be more than one possible transition from a single state given input symbol and stack symbol, while in a DPDA there is only one transition. So, computation of a NPDA looks like a tree, i.e., different branches for different computation paths. Computation halts when you reach a "leaf".

You can think of a computation process on a NPDA like (you suggested) running these branches in parallel where each branch has its own stack. Each branch may accept or reject input. If at least one branch halts with accept then the NPDA accepts that input. Otherwise it rejects.

Alternatively you could think of the computation as breadth first traversal on these branches. There is only one stack. You reuse the stack by restoring its content when you backtrack. You also should remember the position of the head on the input tape and content of the tape. This is the same as you look for the exit from a maze. You try different paths, and when you detect that you hit the dead end you return to the previous position and try different paths.

The latter is suitable for simulation on real computers.

You should also remember that unlike DFAs and NFAs, DPDAs and NPDAs are not equivalent.

Answer 2

That's not how non-determinism works, though perhaps it's how you'd simulate it in real life. Here are several ways of thinking about non-determinism.

The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the machine to do, it will always reject.

Hints. The machine computes a bivariate function. The first input is a word $w$, and the second input is a "hint" $x$. Whenever the machine faces a non-deterministic choice, it consults the next hint symbol, and operates accordingly. We are promised the following:

• Completeness: if $w \in L$ then there is some hint $x$ which causes the machine to accept.
• Soundness: if $w \notin L$ then the machine rejects on all hints.

Accepting computations. An accepting computation is a legal computation (one in which the machine always operates according to one of the choices it is faced with) which ends at an accepting state. A word is in the language iff it has an accepting computation.

We can formalize the notion of accepting computation using snapshots. A snapshot is a triple $(q,z,t)$, where $q$ is the current state, $z$ is the part of the word which remains to be read, and $t$ is the contents of the stack. We can define a relation $(q_1,z_1,t_1) \vdash (q_2,z_2,t_2)$ which expresses that the machine can reach snapshot $(q_2,z_2,t_2)$ from snapshot $(q_1,z_1,t_1)$ in one step. An accepting computation for a word $w$ (for the acceptance condition of emptying the stack) is a sequence $\sigma_0 = (q_0,w,\bot),\sigma_1,\ldots,\sigma_N=(q,\epsilon,\epsilon)$, where $q_0$ is the initial state, $\bot$ is the initial state of the stack, $q$ is an arbitrary state, $\epsilon$ is the empty word/stack, and $\sigma_{i-1} \vdash \sigma_i$ for all $i$.

Another equivalent description is in terms of reachability. Consider a directed graph in which vertices are snapshots and there is an edge from $\sigma$ to $\tau$ if $\sigma \vdash \tau$. An accepting computation is a path from $(q_0,w,\bot)$ to $(q,\epsilon,\epsilon)$, for any state $q$.