5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "we will guess middle every time" -- you will need to get rid of operative intuitions regarding non-determinism; they will lead you astray. Thing of non-deterministic models as declarative definitions. $\endgroup$ – Raphael Aug 2 '17 at 19:36
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So we uses backtracking here if one branch fails.And the branches work one at a time,correct? $\endgroup$ – rahul sharma Aug 2 '17 at 17:37
  • $\begingroup$ Yes. If some branch fails then you don't consider it anymore. But computation may run forever. That's why you should traverse using BFS. This is how we simulate it. $\endgroup$ – fade2black Aug 2 '17 at 17:42
  • $\begingroup$ There are some subtleties in the definition, due to the existence of $\epsilon$ transitions (which are still allowed). Take a look at the Wikipedia definition. $\endgroup$ – Yuval Filmus Aug 2 '17 at 17:44
  • $\begingroup$ How does it conflict? By the definition of the DPDA epsilon transition excludes other transition to so that the transition is unique. Or how does it contradict to the parallel runs of possible branches? $\endgroup$ – fade2black Aug 2 '17 at 18:05
  • $\begingroup$ It's true in execution, but the transition function itself has at most one transition "from a single state given input symbol and stack symbol", and also at most one $\epsilon$-transition; but if it has an $\epsilon$-transition, it is not allowed to have any other transitions. Apparently it is also allowed to get stuck, like in some people's definition of DFA. $\endgroup$ – Yuval Filmus Aug 2 '17 at 18:07
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So practically ,we always take a branch which will eventually succeed looking upon the Hint and never takes a branch which will result in dead end and theoretically it works as @fade2black answered? $\endgroup$ – rahul sharma Aug 2 '17 at 17:40
  • $\begingroup$ Yes, that's one way to view it. fade2black's answer is also valid – there are several different viewpoints. $\endgroup$ – Yuval Filmus Aug 2 '17 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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