How can this all-NFA be converted to an DFA

205 Views Asked by At

an all-NFA was defined in Sipse as such:

A (Q, Σ, δ, q0, F) that accepts x ∈ Σ∗ if every possible state that M could reach after reading input x is in F, so not at least one.

If any branch in an all-NFA computation reaches an implicit or explicit sink state, the input is not accepted.

I am trying to adjust a normal NFA to DFA conversion but I cant quite get this one. Any tips?

1

There are 1 best solutions below

3
On

Such an all-NFA does not accept a word $x$ if and only if there is a state in $Q\setminus F$ that can be reached by processing $x$. So it can be turned into a normal NFA for the complement of your language $L$ by exchanging the final and non-final states, i.e., the NFA $(Q, \Sigma, \delta, q_0, Q \setminus F)$ accepts $\Sigma^* \setminus L$. Now turn this into a DFA for $\Sigma^* \setminus L$ and do the same trick in the resulting DFA to get a DFA for your original language $L$.