# Constuct DFA from NFA with multiple epsilons

I need to create a Deterministic Finite Automata(DFA) from a Nondeterministic Finite Automata(NFA). I have created the NFA, however i'm having a hard time understanding the steps needed to turn the NFA into a DFA. Could someone explain this to me? I'm having a hard time with understanding the epsilons. If I start from state q0. to get an "a" I would need to transition {1, 2, 3, 5, 10}?

NFA: (ac|bc)*

• Did you make this automaton? Why didn't you just combine the transitions labelled $a$ and $b$? You could get rid of states 6, 9 and 7. Also, I don't think 0 and 1 need to be different states, or 2 and 3. – David Feb 17 '16 at 18:04
• The NFA can be simplified to $0 \to 1 \to 0$ where $0 \to 1$ is labelled $a, b$; and $1 \to 0$ is labelled $c$. $0$ is the only accepting state. – David Feb 17 '16 at 18:12

Remember that the states of the DFA are sets of states of the NFA.

Because of the $\epsilon$-transitions, when you’re in state $0$, you’re also simultaneously in states $1,3,4$, and $6$, so the initial state of your DFA will be $\{0,1,3,4,6\}$. And since $3$ is an acceptor state in the NFA, $\{0,1,3,4,6\}$ must be one in the DFA.

If you’re in state $\{0,1,3,4,6\}$ of the DFA and read an $a$, what happens? The only $a$-transition out of $0,1,3,4$, or $6$ in the NFA is the one from $4$ to $8$, so the set of states that you can reach from $\{0,1,3,4,6\}$ on reading an $a$ is simply $\{8\}$; this is another state of your DFA.

Similarly, the $b$-transition out of $\{0,1,3,4,6\}$ must be to the state $\{9\}$ of the DFA: the only $b$-transition in the NFA from any of $0,1,3,4$, and $6$ is the one from $6$ to $9$.

Similar reasoning shows that the DFA must have a $c$-transition from $\{8\}$ to $\{5\}$. But wait: from $5$ there is an $\epsilon$-transitions in the NFA to $2$, from there to $1$ and $3$, and from $1$ to $4$ and $6$, so when the NFA is in state $5$, it is also effectively in states $2,3,1,4$, and $6$. Thus, the $c$-transition out of $\{8\}$ actually goes to the state $\{1,2,3,4,5,6\}$ of the DFA. This contains the original state $3$, so it must be an acceptor state.

You can check similarly that the $c$-transition out of $\{9\}$ in the DFA must go to a state $\{1,2,3,4,6,7\}$, which again must be an acceptor state.

Let’s take a look at the transition table so far to see just what we have. I’ve starred the initial state and underlined the acceptor states.

$$\begin{array}{c|c|c|c} \text{current state}&a&b&c\\ \hline \underline{\{0,1,3,4,6\}^*}&\{8\}&\{9\}\\ \{8\}&&&\underline{\{1,2,3,4,5,6\}}\\ \{9\}&&&\underline{\{1,2,3,4,6,7\}}\\ \underline{\{1,2,3,4,5,6\}}\\ \underline{\{1,2,3,4,6,7\}} \end{array}$$

Let’s start filling in the blanks. What happens if we’re in the initial state $\{0,1,3,4,6\}$ and read a $c$? There is no provision for this in the NFA, so we go nowhere. In other words, the set of states reachable from $\{0,1,3,4,6\}$ by reading a $c$ is the empty set of states, $\varnothing$. We’ll have to add that to the transition table. You can check that the same thing happens if we get an input of $a$ or $b$ to state $\{8\}$ or state $\{9\}$, and of course any input to state $\varnothing$ leaves us there:

$$\begin{array}{c|c|c|c} \text{current state}&a&b&c\\ \hline \underline{\{0,1,3,4,6\}^*}&\{8\}&\{9\}&\varnothing\\ \{8\}&\varnothing&\varnothing&\underline{\{1,2,3,4,5,6\}}\\ \{9\}&\varnothing&\varnothing&\underline{\{1,2,3,4,6,7\}}\\ \underline{\{1,2,3,4,5,6\}}\\ \underline{\{1,2,3,4,6,7\}}\\ \varnothing&\varnothing&\varnothing&\varnothing \end{array}$$

Can you fill in the remaining six transitions? To get you started, if the NFA is in one of the states $1,2,3,4,5$, or $6$ and inputs an $a$, what’s the only state of the NFA that it can reach?

• So then this would refer to the last 6 states: {8}, {9}, ∅ {8}, {9}, ∅ and that would translate to the following DFA: snag.gy/P6PxM.jpg – user1213904 Feb 17 '16 at 18:58
• @user1213904: Yes, that looks right, except that my convention for DFAs requires that every state have a transition for each possible input, so I would include a garbage state $q_5$ corresponding to $\varnothing$ in the table above. – Brian M. Scott Feb 17 '16 at 19:05
• Ok I will, thanks a lot I finally understand it now :D – user1213904 Feb 17 '16 at 19:13
• @user1213904: Glad it helped; you’re welcome! – Brian M. Scott Feb 17 '16 at 19:15