0
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Feb 17 '16 at 18:04
  • $\begingroup$ 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. $\endgroup$ – David Feb 17 '16 at 18:12
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user1213904 Feb 17 '16 at 18:58
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Feb 17 '16 at 19:05
  • $\begingroup$ Ok I will, thanks a lot I finally understand it now :D $\endgroup$ – user1213904 Feb 17 '16 at 19:13
  • $\begingroup$ @user1213904: Glad it helped; you’re welcome! $\endgroup$ – Brian M. Scott Feb 17 '16 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.