# Transforming NFA into DFA

In the examples I was given I have the following NFA diagram:

Then it gives the conversion process

Could someone explain to me the process of obtaining the second column:

{1,2,4} = a{1, 2, 3, 4}, b{1, 4, 5}

• Google "powerset construction". – Raphael Apr 12 '15 at 16:10
• @raphael, where is our reference powerset thread? – Ran G. Apr 12 '15 at 22:24
• @RanG. We don't have one, and I don't think we strictly need to. It's included in any textbook on the matter, and even on Wikipedia (if not very nicely). So this would go under "general reference", I think, and I'd assume everybody who faces an exercise problem like to have seen the algorithm in class. – Raphael Apr 13 '15 at 9:56
• @Raphael the same holds also to several other questions to which we do have a reference question... – Ran G. Apr 13 '15 at 13:58
• @RanG. That is certainly true. However, in most cases I have in mind, there are either a) several methods or b) the methods are not algorithmic so a didactic exposition (!= most stuff on Wikipedia) is advantageous. In this case, there is one algorithm that is immediate to apply, so a reference question can not do more than state the algorithm and maybe one or two examples. Do you disagree? (Nothing prevents you in principle to creating such a post, mind.) – Raphael Apr 13 '15 at 14:48

This is the standard procedure for converting NFAs to DFAs. The first row should be read as "If you know you're in one of the states $0$, $1$ and $4$ and you read an $a$, you'll have to be in one of the states $1$, $2$ and $4$; if you read a $b$, you'll have to be in one of $1$, $4$ and $5$." The other rows are similar.
• $E(0)$ is the start state of the NFA plus all states you can reach from it just using $\epsilon$-transitions. The rest of the state sets in the first column are all of the ones that appear in columns 2 and 3. (You could compute a row for every set of NFA states but it's more efficient to just do the ones that appear in columns 2 and 3.) – David Richerby Apr 12 '15 at 11:58
\begin{align*}\delta_d(\{1, 2, 4\}, a) &= \delta(1, a) \cup \delta(2, a) \cup \delta(4, a)\\ &= \{1, 2, 3, 4\}\\[2ex] \delta_d(\{1, 2, 4\}, b) &= \delta(1, b) \cup \delta(2, b) \cup \delta(4, b)\\ &= \{1, 4, 5\} \end{align*}