Complete list of answers to the list of questions about the regular expression to NFA transformation example

1. • There are 7 operators in the above expression.

     • 3 concatenation operators

     • 3 + operators

     • 1 * operator

2. The last operator of r is the second + operator.

   (ab+b)^* + (a + ba)a

3. • s = (ab+b)^*

   • t = (a+ba)a

4. 1. There are 3 operators in s = (ab+b)^*, one of each type.

   2. The last operator of s is the * operator.

   3. In this case, there is only one subexpression s' = ab+b.

5. All unlabeled arcs in the transition diagram below are transitions.

   

6. All unlabeled arcs in the transition diagram below are transitions.

   

7. All unlabeled arcs in the transition diagram below are transitions.

   

8. All unlabeled arcs in the transition diagram below are transitions.

   

9. • We are showing that every regular expression can be converted into an equivalent NFA using a single proof that applies to any regular expression r.

   • The basic property of regular expressions that we used was the fact that every regular expression has finite length and thus a finite number of operators.

   • Once this property was established, we could apply an induction proof to complete the argument.

10. • Transform(r)

      • Base Case

        • If r has no operators, then return the corresponding NFA for r

          • There are only a finite number of cases to consider, and I do not list these here as they have been listed above in the proof.

      • Recursive Case

        • Identify the "last operator" of r

        • Decompose r into s and t using this last operator (note t will not exist if the last operator is a *)

        • N_s = Transform(s)

        • N_t = Transform(t) (if t exists)

        • Put N_s and N_t together according to the rules described in the proof to form N_r

        • Return N_r