In the examples I was given I have the following NFA diagram: enter image description here

Then it gives the conversion processenter image description here

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

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

  • 1
    $\begingroup$ Google "powerset construction". $\endgroup$ – Raphael Apr 12 '15 at 16:10
  • $\begingroup$ @raphael, where is our reference powerset thread? $\endgroup$ – Ran G. Apr 12 '15 at 22:24
  • $\begingroup$ @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. $\endgroup$ – Raphael Apr 13 '15 at 9:56
  • $\begingroup$ @Raphael the same holds also to several other questions to which we do have a reference question... $\endgroup$ – Ran G. Apr 13 '15 at 13:58
  • $\begingroup$ @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.) $\endgroup$ – 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.

  • $\begingroup$ Thanks for the nice answer, just an additional question how do we get the initial states for the two rows? ie. E(0) = {0, 1, 4}, E(1) = {1, 2, 4} $\endgroup$ – Kadana Kanz Apr 12 '15 at 11:53
  • $\begingroup$ $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.) $\endgroup$ – David Richerby Apr 12 '15 at 11:58

You should do

$$\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*}$$


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.