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.

First post here, woot. I've been a member of Stack Overflow for a while, so hopefully you guys are just as friendly!

The DFA

I'm having issues converting simple NFAs to DFAs... I just don't get it. Basically, with the one shown here, the most I've come up with is $s_0$ accepting inputs of $1$ from $s_1$ and $s_1$ accepting inputs of $0$ from $s_0$. Is that even remotely correct? FSM's are interesting... but bloody hell, the learning material is a bit difficult to chew.

For those that don't know the acronyms, I'm basically trying to find the deterministic finite-state automaton equivalent of the pictured non-deterministic finite-state machine.

share|improve this question
    
Have you figured out how many states your DFA is going to have? –  Unreasonable Sin Dec 14 '11 at 4:59
    
This question would have been perfect for the upcoming Computer Science Stack Exchange. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! –  Raphael Dec 15 '11 at 13:15
1  
An algorithm for this task is probably given in any basic TCS textbook. Have you checked one? –  Raphael Dec 15 '11 at 13:16

2 Answers 2

To convert from a NFA to DFA you have to keep track of all the possible states the NFA might be in. So the set of states for your DFA will be $\lbrace \emptyset, s_0, s_1, s_2, s_0s_1, s_0s_2, s_1s_2, s_0s_1s_2 \rbrace$.

In the NFA, if you're in the start state $s_0$ and you read a $0$ then you transition to both $s_1$ and $s_2$. In the DFA this is done by transitioning from $s_0$ to $s_1s_2$. In the NFA, if you're at $s_2$ and read a $0$ or $1$ what happens? The input gets rejected. For the DFA this is accomplished by having a null state $\emptyset$ that does not transition to any other state, but instead has a self-loop for either $0$ or $1$.

You can check your DFA by figuring out what language this NFA accepts. It's any number of $1$'s followed by a $0$, and then any number of $0$'s, which as a regular expression is $1^*00^*$.

share|improve this answer

The usual approach is to is to give the DFA a state for each set of states in the NDFA. In your case those are $t_\varnothing,t_0,t_1,t_2,t_{01},t_{02},t_{12}$, and $t_{012}$. That is, $t_{02}$, for instance, is a state of the DFA corresponding to the set $\{s_0,s_2\}$ of states of the NDFA.

The NDFA has a unique initial state, $s_0$, so its set of initial states is $\{s_0\}$, and we make $t_0$ the initial state of the DFA. An input of $0$ in state $s_0$ can take you to either $s_1$ or $s_2$ in the NDFA, so $\{s_1,s_2\}$ is the set of possible resulting states; this corresponds to $t_{12}$ in the DFA that we’re building, so we give it the transition $$t_0\;\stackrel{0}\longrightarrow\; t_{12}\;.$$

An input of $1$ to the NDFA in state $s_0$ takes it only to $s_0$, so $\{s_0\}$ is the set of possible resulting states, corresponding to $t_0$, and we must have a transition $$t_0\;\stackrel{1}\longrightarrow\;t_0$$ in the DFA.

What happens if I’m in one of the states in the set $\{s_1,s_2\}$ in the NDFA and get an input of $0$? If I’m in $s_1$, I go to $s_1$, and if I’m in $s_2$, no further computation is possible. The only $0$ transition from either of these states goes to $s_1$, so the set of possible resulting states is just $\{s_1\}$, and in the DFA the $0$ transition from $t_{12}$ must be to $t_1$: $$t_{12}\;\stackrel{0}\longrightarrow\;t_1\;.$$ Similar reasoning gives you the DFA transition $$t_{12}\;\stackrel{1}\longrightarrow\;t_2\;.$$

Now we need to compute the DFA $0$ and $1$ transitions for the states $t_1$ and $t_2$. You should have no trouble with $t_1$, but $t_2$ introduces a new wrinkle: neither input goes anywhere. This just means that the set of possible resulting states is $\varnothing$, the empty set, and the DFA transitions are $$t_2\;\stackrel{0}\longrightarrow\;t_\varnothing$$ and $$t_2\;\stackrel{1}\longrightarrow\;t_\varnothing\;.$$

Now that $t_\varnothing$ has appeared, we need to calculate the $0$ and $1$ transitions from it; they should be pretty clear after what we just did for $t_2$.

When you’ve filled in the blanks, you’ll find that the states $t_{01},t_{02}$, and $t_{012}$ never arose; you can still fill in transitions for them, but you need not, since these states are inaccessible from the initial state $t_0$.

One last task remains: to determine the acceptor state(s) of the DFA. That’s easy: if a set of NDFA states includes at least one acceptor state, the corresponding DFA state is an acceptor state. Here that means that $t_1,t_{12},t_{01}$, and $t_{012}$ are acceptor states, though we can ignore the last two, since they’re inaccessible.

share|improve this answer
1  
The last paragraph is wrong. A DFA state should be accepting if its defining set contains at least one NFA accepting states. It can contain non-accepting states, and it does not have to contain all of the NFA acceptors. –  Henning Makholm Dec 14 '11 at 13:40
    
@Henning: You’re right. That was a careless last-minute addition, and I wasn’t thinking. Fixed. –  Brian M. Scott Dec 14 '11 at 19:16

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.