NFA to FA

On this page, we have an example NFA N which we will convert to an equivalent FA M. You will be quizzed to test your understanding of this conversion process.

1. What exactly do we mean by "an equivalent FA M? That is, what is our goal for M?

2. Based only on the fact that this NFA N has 3 states, what is an upper bound on the number of states needed in the equivalent FA M?

3. Suppose we characterize the strings of {a + b}^* in the following manner.
   • L(I) is the set of strings which might cause the NFA N to end up in state I.
   • L(II) is the set of strings which might cause the NFA N to end up in state II.
   • L(III) is the set of strings which might cause the NFA N to end up in state III.

   Using the categories L(I), L(II), and L(III), how would you characterize the strings which cause the FA M to end up in state {I,III}?

4. What states can the NFA N get into when it has only processed the input string ?

5. Which state should be the initial state of the FA M?

6. Which states should be accepting states of the FA M?

7. What state should the FA M transition to when it is in state {I,III} and processes the input character a?

8. What state should the FA M transition to when it is in state {II,III} and processes the input character a?

Click here for a transition diagram of the FA M. You may wish to construct the transition diagram of M first on your own and compare.