3
$\begingroup$

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.

  • 1
    An algorithm for this task is probably given in any basic TCS textbook. Have you checked one?2011-12-15

2 Answers 2

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^*$.

2

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.

  • 0
    @Henning: You’re right. That was a careless last-minute addition, and I wasn’t thinking. Fixed.2011-12-14