# Use the construction in Theorem 3.1 to find an nfa that accepts the language L (ab*aa + bba*ab)….

Use the construction in Theorem 3.1 to find an nfa that accepts the language L (ab*aa + bba*ab).

Theorem 3.1

Let r be a regular expression. Then there exists some nondeterministic finite accepter that accepts L(r). Consequently, L(r) is a regular language. Proof: We begin with automata that accept the languages for the simple regular expressions Ø,λ, and a ∈ Σ. These are shown in Figure 3.1(a) , (b), and (c), respectively. Assume now that we have automata M (r1 ) and M (r2 ) that accept languages denoted by regular expressions r1 and r2 , respectively. We need not explicitly construct these automata, but may represent them schematically, as in Figure 3.2. In this scheme, the graph vertex at the left represents the initial state, the one on the right the final state. In Exercise 7, Section 2.3, we claim that for every nfa there is an equivalent one with a single final state, so we lose nothing in assuming that there is only one final state. With M (r1 ) and M (r2 ) represented in this way, we then construct automata for the regular expressions r1 + r2 , r1r2 , and . The constructions are shown in Figures 3.3 to 3.5. As indicated in the drawings, the initial and final states of the constituent machines lose their status and are replaced by new initial and final states. By stringing together several such steps, we can build automata for arbitrary complex regular expressions. It should be clear from the interpretation of the graphs in Figures 3.3 to 3.5 that this construction works. To argue more rigorously, we can give a formal method for constructing the states and transitions of the combined machine from the states and transitions of the parts, then prove by induction on the number of operators that the construction yields an automaton that accepts the language denoted by any particular regular expression. We will not belabor this point, as it is reasonably obvious that the results are always correct.