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)*
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?