Closure Properties of Regular Languages
Regular languages are closed under many operations, meaning: if you take regular languages and apply these operations, the result is still regular. These properties are powerful tools for proving languages are regular (or not regular) and for constructing new automata from existing ones.
The Closure Properties
Regular languages are closed under:
1. Union: L1 ∪ L2
If L1 and L2 are regular, L1 ∪ L2 is regular.
2. Intersection: L1 ∩ L2
If L1 and L2 are regular, L1 ∩ L2 is regular.
3. Complement: L̄ (complement of L)
If L is regular, its complement is regular.
4. Concatenation: L1 · L2
If L1 and L2 are regular, L1L2 is regular.
5. Kleene Star: L*
If L is regular, L* is regular.
6. Reversal: L^R
If L is regular, the set of reversed strings is regular.
7. Homomorphism: h(L)
If L is regular and h is a homomorphism, h(L) is regular.
8. Inverse Homomorphism: h⁻¹(L)
If L is regular and h is a homomorphism, h⁻¹(L) is regular.
9. Difference: L1 \ L2
If L1 and L2 are regular, L1 \ L2 is regular.Why These Matter
Closure properties give you shortcuts. If you need to prove that a language L = L1 ∪ L2 is regular, you don't need to build a DFA from scratch. Just prove L1 and L2 are regular (by providing DFAs or regexes), then apply the closure property.
They also help prove non-regularity. If a language L can be expressed as L1 ∩ L2 where L2 is regular but L1 is not, and you know regular languages are closed under intersection, you can reason about the result.
Example:
L1 = strings with even number of 0s (regular)
L2 = strings ending in 1 (regular)
L1 ∩ L2 = strings with even 0s AND ending in 1
(regular, by closure under intersection)
Build DFA for L1 ∩ L2 by taking the product of
the two DFAs. Each state is a pair (state from
DFA1, state from DFA2).Product Construction for Intersection
To build a DFA for L1 ∩ L2 from DFAs D1 and D2:
Given:
D1 = (Q1, Σ, δ1, q01, F1) — DFA for L1
D2 = (Q2, Σ, δ2, q02, F2) — DFA for L2
Product DFA:
States: Q1 × Q2
Start: (q01, q02)
Accept: F1 × F2 (both accept)
δ((s1, s2), a) = (δ1(s1, a), δ2(s2, a))
For union (L1 ∪ L2):
Accept: (F1 × Q2) ∪ (Q1 × F2)
(at least one accepts)
For complement (L̄):
Accept: Q \ F (swap accept/non-accept states)