Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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. enter image description here

share|cite|improve this question
up vote 14 down vote accepted

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

share|cite|improve this answer
To expand, the reason for introducing non-determinism is that it simplifies solving many problems. At first blush, it might seem to allow us to solve actually more problems than DFAs. The conversion from any NFA to a DFA shows that the non-determinism does not allow us to do more. But it still allows us to do more simply. – TNi Aug 3 '11 at 13:41
However, it should be noted that sometimes the DFA is exponenitally more complex than the NFA, when complexity is measured by the number of states. – Gadi A Aug 3 '11 at 14:56
@Gadi A: Thanks a lot ;) – Chan Aug 3 '11 at 19:20

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.

share|cite|improve this answer
Thanks a lot for the explanation. – Chan Aug 3 '11 at 19:25

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.

share|cite|improve this answer


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.


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.

share|cite|improve this answer

I'm a noob at automata. As, far as I know, there is no unique solution for a conversion from DFA to NFA. Therefore, your answer is not challengeable. Although, you can try and make the tightest possible state diagram.

Whereas, when you are converting an NFA to DFA , you will find a unique solution.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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