2.5 Finite Automata and Regular Expressions 57
Figure 2.39: NFA with a single final state.Theorem 2.31 Let L be a language. The following are equivalent:
(a) L is a regular language.
(b) There is a DFA M such that L(M) = L.
(c) There is an NFA A4 such that L(M) = L.
Example 2.32 Find a regular expression for the language accepted by NFA
in Figure 2.29(a).
Solution. By using the above method, we can compute a regular expression
for the language accepted by NFA in Figure 2.29(a) as shown in Figure 2.40.
First, we create a new unique final state and then eliminate state 45. Then,
we eliminate states 41, q2, q3 and q4, one at a time. Finally, we use the basis
step to get the regular expression (0 + l)(Ol + lO)O from the last digraph.
Exercise 2.5
1.
For each of the following regular expressions r, construct a DFA that
accepts L(r):
(a) (0 + lO)*(l+ Ol)*.
(b) (0 + l)*O(O + l)(O + l)O(O + l)*
(c) o(0 + 1>*0 + l(0 + 1)*1.
For each of the following languages, find an NFA that accepts it:(a) {X#Y I X:,Y E (0 + I)“, I4 = IYI (mod 2))*
(b) {X#Y I ?Y E (0 + 1>*, I4 + IYI 2 XI*
(c) {z#y I X, y E (0 + l)*, 1x1 l IyI is dividable by 5).Figure 2.41 shows an NFA accepting O*, constructed based on the
method of Example 2.22. The four E-moves cannot be eliminated by the
rule of Theorem 1.25. Apply the method in the proof of Theorem 2.31
to reduce some of its E-moves. Can you find, from this example, a more
general rule (than Theorem 1.25) to eliminate redundant E-transitions?