Theorem 1.54: A language is regular if and only if some regular expression describes it.

This theorem has two directions. We state and prove each direction as a separate lemma.

1. Consider the state diagram of a deterministic finite automaton M, shown in Exercise 1.21(b) on page 86. (a) Draw the state diagram of an equivalent GNFA G. You do not need to show empty-set transitions. (b) Reduce G to a 2-state GNFA H by using the technique of our proof of Theorem 1.54. (c) Give a regular expression R equivalent to M by using the result of part (b) above