Convert from DFA to NFA

Question

For this language $\{ w \mid w \text{ contains at least three 1's} \}$, its DFA diagram is defined as follows:

While trying to convert it to NFA, but I realized that its NFA would be identical to its DFA. I'm not sure is it possible or not since I know there is a procedure to convert from NFA to DFA. Does NFAs always require a $\varepsilon$ transition or a transition which has one input goes to two states? If it does, I could just add a $\varepsilon$ transition; though, it doesn't mean much.

Answer 1

A NFA can, by definition, be exactly identical to a DFA; there is no need to induce some nondeterminism "by force".

Answer 2

In the definition of a NFA the transition function takes as its inputs the current state and symbol to be processed, and produces a set of states. This is in contrast to a DFA whose transition function only produces a single state.

For the problem given, it's true that the state diagrams of the NFA and the DFA will be identical. However the transition function for the NFA will be producing a set of states. It just so happens that all these sets of states contain a single element.

Answer 3

For finite automata, nondeterminism does not speed up the computation for this problem, and in fact the DFA and NFA are the same (as explained in the other answers) because there is no natural way to exploit nondeterminism to skip the reading of the string.

However, for other models of computation, a nondeterministic machine can solve the problem faster by guessing the location of three distinct 1's in the string and verifying that 1's are in those locations, while a deterministic algorithm has to read the entire string in the worst case. For a RAM this is $O(\log n)$ operations for the nondeterministic algorithm and $O(n)$ for the deterministic one.

Answer 4

Chan,

Lets's say we have a DFA $D$ and we want to construct a NFA $N$, such that $L(D) = L(N)$. Then the construction would be as follows:

Let's assume that the DFA $D$ has the state set $Q = \{q_0, q_1, ..., q_n\}$.

Now, we "build" the NFA $N$ as follows:

($1$.) Start with the DFA $D$.

($2$.) Add an additional accepting state for the NFA $N$, such that $N$ will have $n + 1$ total number of states.

Let's call the new accepting state $q_{n + 1}$.

($3$.) Now, add an epsilon $\epsilon$ transition from all accepting states to the new accepting state $q_{n + 1}$, and make all the original accepting states just normal states.

DONE.

Now, we have an NFA $N$ such that $L(N) = L(D)$.

Note: Any of the states in the set $Q$ could be an accepting state. By making them regular states and adding epsilon $\epsilon$ transitions from them to our created accepting state, we have successfully built an NFA. This construction can work for any DFA.

Additional note: One variation of the above construction would be to add an additional start state as well, and make an epsilon $\epsilon$ transition from the new start state to the original start state.