Proof: If L 1 and L 2 are regular, then there exist regular expressions r 1 and r2
such that L 1 = L(r 1 ) and L 2 = L(r 2 ). By definition, r 1 + r 2 , r 1 r 2 , and are regular
expressions denoting the languages L 1 ∪ L 2 , L 1 L 2 , and , respectively. Thus,
closure under union, concatenation, and star-closure is immediate.
To show closure under complementation, let M = (Q, Σ,δ, q 0 ,F) be a dfa that
accepts L 1 . Then the dfa
accepts
. This is rather straightforward; we have already suggested the result
in Exercise 4 in Section 2.1. Note that in the definition of a dfa, we assumed δ *
to be a total function, so that δ * (q o ,w) is defined for all w ∈ Σ * . Consequently
either δ * (q 0 ,w) is a final state, in which case w ∈ L, or δ * (q 0 , w) ∈ Q − F and w
∈ .
Demonstrating closure under intersection takes a little more work. Let L 1 = L
(M 1 ) and L 2 = L (M 2 ), where M 1 = (Q,Σ,δ 1 ,q 0 ,F 1 ) and M 2 = (P,Σ, δ 2 ,p 0 ,F 2 ) are
dfa's. We construct from M 1 and M 2 a combined automaton
,
whose state set
consists of pairs (q i , p j ), and whose transition function
is such that is in state (q i , p j ) whenever M 1 is in state q i and M 2 is in state p j .
This is achieved by taking
whenever
and
is defined as the set of all (q i , p j ), such that q i ∈ F 1 and p j ∈ F 2 . Then it is a
simple matter to show that w ∈ L 1 ∩ L 2 if and only if it is accepted by .
Consequently, L 1 ∩ L 2 is regular.