Problem Solving in Automata, Languages, and Complexity

58 FINITE AUTOMATA

O+l^0 O+l

01

Figure 2.40: Finding a regular expression from an NFA.

Figure 2.41: An NFA accepting O*.

4. For each of the languages accepted by NFA’s of Figure 2.42, find a
   regular expression for it.

2.6 Closure Properties of Regular Languages

In Theorem 2.31, we have shown that a regular language has three types

of representations: regular expressions, DFA’s and NFA’s. This equivalence