0
$\begingroup$

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}

$\endgroup$
5
  • 1
    $\begingroup$ Google "powerset construction". $\endgroup$
    – Raphael
    Apr 12, 2015 at 16:10
  • $\begingroup$ @raphael, where is our reference powerset thread? $\endgroup$
    – Ran G.
    Apr 12, 2015 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, 2015 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, 2015 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, 2015 at 14:48

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Apr 12, 2015 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$ Apr 12, 2015 at 11:58
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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