Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For this language $\{ w | 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|improve this question
add comment

4 Answers

up vote 12 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|improve this answer
3  
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
add comment

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|improve this answer
    
Thanks a lot for the explanation. –  Chan Aug 3 '11 at 19:25
add comment

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|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.