2.6 Closure Properties of Regular Languages 59
(4 W
Figure 2.42: Two NFA’s for Exercise 4.result provides us with useful tools to manipulate regular expressions or finite
automata to get new regular expressions or finite automata. In this section,
we apply these tools to prove that regular languages are closed under many
language operations @, in the sense that if a given language L is regular then
the language Q(L) is also a regular language. Furthermore, most results are
proved by constructive methods.
We start with the most common language operations introduced in Section
1.1.
Theorem 2.33 The class of regular languages is closed under union, inter-
section, subtraction, complementation, concatenation, Kleene closure and re-
versal.Proof. We showed in Section 2.2 how to construct, from two given DFA’s A&
and A& new DFA’s to accept the union, the intersection and the difference
of languages L(M1) and L(M& as well as the complement of L(M,). Fur-
thermore, we showed in Examples 2.21 and 2.22 how to construct, from two
given NFA’s Ms and A& NFA’s to accept the concatenation and the Kleene
closure of L(M3) and L(Md).
Finally, we can prove by induction that if L is regular then LR is regular
(cf. Example 1.21). First, for the basis step, we check that @JR = 8, {E}~ = {E}
and {a}R = {a}. Next, for the induction step, we recall from Example 1.8
that (AB)R = BRAR and (A U B)R = AR U BR. Furthermore, use a similar
proof of Example 1.8, we can prove that (A)R = (AR). Thus, the induction
step is complete.^0
The following example presents a more constructive mehtod for proving
that regular languages are closed under reversal.
Example 2.34 Let M be an NFA. Construct an NFA M’ such that L(M’) =
L(M)R.Solution. From the last example, we can first find a regular expression r such
that L(r) = L(M). Next, we get a regular expression s such that L(s) =