The proof of closure under intersection is a good example of a constructive
proof. Not only does it establish the desired result, but it also shows explicitly
how to construct a finite accepter for the intersection of two regular languages.
Constructive proofs occur throughout this book; they are important because they
give us insight into the results and often serve as the starting point for practical
algorithms. Here, as in many cases, there are shorter but nonconstructive (or at
least not so obviously constructive) arguments. For closure under intersection,
we start with DeMorgan's law, Equation (1.3), taking the complement of both
sides. Then
for any languages L 1 and L 2 . Now, if L 1 and L 2 are regular, then by closure under
complementation, so are
and . Using closure under union, wenext get that
is regular. Using closure under complementation once more, we see that
is regular.
The following example is a variation on the same idea.
Example 4.1
Show that the family of regular languages is closed under difference. In other
words, we want to show that if L 1 and L 2 are regular, then L 1 − L 2 is necessarily
regular also.
The needed set identity is immediately obvious from the definition of a set
difference, namely
The fact that L 2 is regular implies that is also regular. Then, because of the
closure of regular languages under intersection, we know that
is regular,
and the argument is complete.
A variety of other closure properties can be derived directly by elementary