Complete list of answers to the questions asked about the NFA to FA example.

1. Our goal is to create an FA M such that L(M) = L(N).

2. Our upper bound on the number of states in M is 2³ = 8. In general, if the NFA N had q states, the upper bound would be 2^q.

3. The strings that cause the FA M to end up in state {I,III} are
   (L(I) intersection L(III)) - (L(I) intersection L(II) intersection L(III)).

   How would you generalize this notion to an arbitrary FA M that simulates an arbitrary NFA N?

4. {I,III}

   The NFA N can be in the state I because it is the initial state of N.

   It can also be in state III because of the transition from state I to state III.

5. Because of the previous answer, the initial state of the FA M should be {I,III}.

6. The accepting states of FA M should be {III},{I,III},{II,III}, and {I,II,III}.

   In general, the accepting states of M should be any subset of the state set of N that includes an accepting state.

   In this case, any subset of {I,II,III} that includes state III.

7. The NFA N can transition to states I and II on character a from state I. Furthermore, because of the transition between states I and III, it can get to state III as well.

   Meanwhile, the NFA N can transition to state III on character a from state III.

   The answer is the union of these two sets which is {I,II,III}.

8. The NFA N can transition to states II and III on character a from state II.

   Meanwhile, the NFA N can transition to state III on character a from state III.

   The answer is the union of these two sets which is {II,III}.

9. state q	(q,a)	(q,b)
   {}	{}	{}
   I	I,II,III	II,III
   II	II,III	I,III
   III	III	II
   I,II	I,II,III	I,III
   I,III	I,II,III	I,II,III
   II,III	II,III	I,II,III
   I,II,III	I,II,III	I,II,III

   I left out the braces except for the empty set because I found them to be visually confusing.