Chapter 15 of 34

Closure Properties of Regular Languages

Suppose you have a DFA that checks "the password contains a digit" and another that checks "the password has length at least 8". Can a single finite automaton check both at once? Can one check "contains a digit but is not longer than 20"? If every such combination of regular languages is again regular, you can build complicated checkers out of simple ones without ever leaving the world of finite automata.

That is what closure properties are about.

The class of regular languages is closed under an operation if applying that operation to regular languages always produces a regular language.

In this chapter we prove that regular languages are closed under union, concatenation, star, complement, intersection, difference, reversal, homomorphism, inverse homomorphism, quotient and more, each with a concrete construction. We then use closure as a tool to prove that some languages are not regular, look at what closure does not promise, and finish with the decision properties of regular languages. All the example machines in this chapter were checked by simulation on every string up to length 10.


What "Closed" Means (and What It Does Not)

Integers are closed under + and ×: adding two integers gives an integer. They are not closed under ÷: 1 ÷ 2 is not an integer. In the same way:

  • "Regular languages are closed under ∪" means: if L1 and L2 are regular, then L1 ∪ L2 is regular.

  • It says nothing about non-regular inputs. If L1 or L2 is not regular, L1 ∪ L2 may or may not be regular.

  • "Not closed under X" means there is at least one example where regular inputs give a non-regular output. It does not mean the output is always non-regular.

To prove closure we always do the same thing: take machines (or regular expressions) for the inputs and build one for the output.


The Regular Operations: Union, Concatenation, Star

These three are immediate from the definition in Regular Expressions: if L1 = L(R1) and L2 = L(R2), then

Operation

Regular expression

Automaton construction

L1 ∪ L2

R1 + R2

new start state with ε-arrows to both start states

L1L2

R1R2

ε-arrows from M1's accepting states to M2's start

L1*

R1*

the star gadget of Thompson's construction

The machine constructions are exactly the gadgets of Regular Expression to Finite Automata. By repeated use, regular languages are closed under any finite union and concatenation, and under L+ = LL*.


Complement

If L is regular over Σ, then its complement L̄ = Σ* − L is regular.

Construction: take a complete DFA M for L (every state has an arrow for every symbol, adding a dead state if necessary) and swap accepting and non-accepting states. On any input the DFA ends in exactly one state; the new machine accepts exactly when the old one rejects.

Two conditions matter, and both are classic exam traps:

  • The DFA must be complete. If a missing arrow makes the old DFA "fall off" and reject, the swapped machine falls off too and still rejects, so those strings are lost. Add the dead state first (see Deterministic Finite Automata (DFA)).

  • It must be a DFA, not an NFA. An NFA accepts if some path accepts; swapping only makes it accept if some path rejects, which is a different thing.

Counterexample for the NFA trap. This NFA accepts strings ending with a:

State

a

b

→ q0

{q0, q1}

{q0}

* q1

∅

∅

Swapping makes q0 accepting and q1 non-accepting. But q0 is reachable on every input (it loops on both symbols), so the swapped NFA accepts all strings, not "strings not ending with a". The fix: convert to a DFA first with the subset construction, then swap.


Intersection and Difference: The Product Construction

Closure under intersection follows from De Morgan's law, L1 ∩ L2 = complement(L̄1 ∪ L̄2), since we already have union and complement. But there is a direct and much more useful construction: run both DFAs at the same time.

Given complete DFAs M1 = (Q1, Σ, δ1, p0, F1) and M2 = (Q2, Σ, δ2, q0, F2), the product DFA has:

States:      Q1 × Q2               (pairs (p, q))
Start:       (p0, q0)
Transition:  δ((p, q), a) = ( δ1(p, a), δ2(q, a) )
Accepting:   choose according to the operation

Operation

Accepting pairs (p, q)

L1 ∩ L2

p ∈ F1 and q ∈ F2

L1 ∪ L2

p ∈ F1 or q ∈ F2

L1 − L2

p ∈ F1 and q ∉ F2

L1 ⊕ L2 (symmetric difference)

exactly one of p ∈ F1, q ∈ F2

One product machine, four operations: only the accepting set changes. If M1 has m states and M2 has n, the product has at most m × n states.

Worked example

Σ = {a, b}. L1 = even number of a's (states E = even, O = odd). L2 = strings ending with b (states X = last symbol is not b, or empty; Y = last symbol is b).

M1

a

b

→ * E

O

E

O

E

O

M2

a

b

→ X

X

Y

* Y

X

Y

Product (each component moves independently):

State

a

b

∩

∪

L1 − L2

→ EX

OX

EY

accept

accept

EY

OX

EY

accept

accept

OX

EX

OY

OY

EX

OY

accept

Trace "abab": EX –a→ OX –b→ OY –a→ EX –b→ EY. It ends in EY: even a's (2) and ends with b, so it is in L1 ∩ L2. As a bonus, a regular expression for the ∩ language is (b + ab*a)*b: "even a's" followed by a final b (checked against the product DFA).

The product construction also works for NFAs when computing intersection (both must have an accepting path), but for difference and complement you need DFAs.


Reversal

LR = { wR : w ∈ L }, all strings of L written backwards.

Construction: take an automaton for L, reverse every arrow, make the old start state the only accepting state, and add a new start state with ε-arrows to all old accepting states. A path spelling w from start to accept becomes a path spelling wR in the new machine.

With regular expressions it is even easier: reverse the order of every concatenation, recursively. (a(a + b)*)R = (a + b)*a: "starts with a" reversed is "ends with a".


Homomorphism and Inverse Homomorphism

A homomorphism h replaces each symbol by a fixed string: h : Σ → Δ*, extended to strings by h(a1a2…an) = h(a1)h(a2)…h(an).

Homomorphism: h(L) is regular

Construction: in a regular expression for L, replace every symbol a by (h(a)).

Example: h(a) = 01, h(b) = 1, L = a*b. Then h(L) = (01)*1 = { 1, 011, 01011, … }.

Inverse homomorphism: h−1(L) is regular

h−1(L) = { w ∈ Σ* : h(w) ∈ L }: all strings whose image lands in L.

Construction: take a DFA M for L and build M' with the same states, where reading a in M' jumps to wherever M would go after reading the whole string h(a):

δ'(q, a) = δ̂(q, h(a))           (same start state, same accepting states)

Then M' on w ends exactly where M ends on h(w), so M' accepts w iff h(w) ∈ L.

Example: h(a) = 0, h(b) = 11, L = 0*1* (no "10"). A string w maps into 0*1* exactly when no b comes before an a, so h−1(L) = a*b*.

Inverse homomorphism is mostly a proof tool: it lets you transform a language into one where a known non-regularity result applies.


Quotient, Prefix and Suffix

Right quotient

L1/L2 = { x : xy ∈ L1 for some y ∈ L2 }: the strings you get by chopping a suffix belonging to L2 off strings of L1.

Theorem: if L1 is regular, L1/L2 is regular for any language L2 (it need not even be regular).

Construction: keep the DFA for L1, change only the accepting states: q is accepting in the new DFA iff some y ∈ L2 leads from q to an accepting state of the old DFA. (When L2 is regular, this set of states can be computed; for arbitrary L2 it still exists, which is all that closure needs.)

L1

L2

L1/L2

(a + b)*abb

b

(a + b)*ab

a*ba*

ba*

a*

Prefix and suffix

  • Prefix(L) = all prefixes of strings in L. Make every state from which some accepting state is reachable an accepting state. Example: Prefix((ab)*) = (ab)*(ε + a).

  • Suffix(L) = all suffixes. Add a new start state with ε-arrows to every state reachable from the original start state. (Or: Suffix(L) = (Prefix(LR))R.)


The Complete Table

Operation

Closed?

How

Union, finite union

Yes

R1 + R2, or product with "or"

Concatenation

Yes

R1R2

Kleene star, L+

Yes

R*, RR*

Complement

Yes

swap accepting states of a complete DFA

Intersection, finite intersection

Yes

product construction

Difference, symmetric difference

Yes

product construction

Reversal

Yes

reverse arrows

Homomorphism

Yes

substitute h(a) in the regex

Inverse homomorphism

Yes

δ'(q, a) = δ̂(q, h(a))

Substitution by regular languages

Yes

replace each symbol by a regex

Quotient by any language

Yes

change accepting states

Prefix, suffix

Yes

change accepting / start states

Infinite union

No

see below

Infinite intersection

No

complement of an infinite union

Subset

No

a subset of a regular language can be anything

Why infinite union fails

Each single language { anbn } (for a fixed n) has one string, so it is finite and regular. But their union over all n ≥ 0 is { anbn : n ≥ 0 }, which is not regular. A finite union only multiplies the number of states by a fixed amount; an infinite union would need infinitely many states. In fact every language is an infinite union of one-string (regular) languages, so infinite union cannot preserve anything.

Why subset fails

{ anbn : n ≥ 0 } ⊆ a*b*, and Σ* contains every language. Being inside a regular language tells you nothing.


Using Closure to Prove Non-Regularity

Closure properties give a powerful shortcut. Assume we know one language is not regular. We will use the standard fact that B = { anbn : n ≥ 0 } is not regular (a finite automaton cannot count n; the formal proof is in Pumping Lemma for Regular Languages).

The pattern: to show L is not regular, assume it is, combine it with regular languages using closed operations, and arrive at B. Contradiction.

Example 1: equal numbers of a's and b's

L = { w ∈ {a, b}* : #a(w) = #b(w) }.

Assume L is regular.
a*b* is regular.
L ∩ a*b* = { aⁿbⁿ : n ≥ 0 } = B          (in a*b*, equal counts means aⁿbⁿ)
Regular languages are closed under ∩, so B would be regular.  Contradiction.
Hence L is not regular.

Example 2: unequal numbers

L = { anbm : n ≠ m }. Pumping this one directly is awkward, but closure makes it easy:

Assume L is regular. Then its complement L̄ is regular.
L̄ ∩ a*b* = { aⁿbⁿ : n ≥ 0 } = B      (strings of the form a*b* that are not in L)
So B is regular.  Contradiction.

Both set identities were checked by brute force for all strings up to length 10.

Warning: closure only works in the forward direction. "L ∩ R is regular" does not prove that L is regular (for example B ∩ ∅ = ∅ is regular).


Decision Properties of Regular Languages

Closure tells us what we can build; decision properties tell us what we can compute about a regular language given as a DFA, NFA or regex. For regular languages, all the natural questions are decidable:

Question

Algorithm (on a DFA with n states)

Membership: is w ∈ L?

run the DFA on w: O(|w|) steps

Emptiness: is L = ∅?

is any accepting state reachable from the start? (graph search)

Finiteness: is L finite?

L is infinite iff there is a cycle on some path from the start to an accepting state; equivalently, iff it accepts some w with n ≤ |w| < 2n

Universality: is L = Σ*?

is the complement empty?

Subset: is L1 ⊆ L2?

is L1 ∩ L̄2 empty? (product + emptiness)

Equivalence: is L1 = L2?

is L1 ⊕ L2 empty? Or minimise both DFAs and compare them (see DFA Minimization)

Notice how closure properties make the decision algorithms possible: subset and equivalence are reduced to emptiness by building product machines. For context-free languages, several of these questions (universality, equivalence) become undecidable, as we will see later in the course.


Common Mistakes

  • Complementing an NFA or a partial DFA by swapping accepting states. Determinise and complete it first.

  • Reading closure backwards. "L1 ∪ L2 is regular" does not mean L1 and L2 are regular: anbn ∪ Σ* = Σ*.

  • Applying closure to non-regular inputs. Regular ∩ non-regular may be regular (∅ ∩ L = ∅) or not (Σ* ∩ L = L).

  • Thinking subsets of regular languages are regular. anbn ⊆ a*b*.

  • Using infinite unions of regular languages and expecting a regular result.

  • Forgetting the accepting set in the product construction: the same product machine gives ∩, ∪, − and ⊕ depending only on the accepting pairs.


GATE-Style Questions

Q1. L1 is regular and L2 is not. Which of L1 ∪ L2, L1 ∩ L2 must be non-regular?

Neither. With L1 = Σ*: the union is Σ* (regular) and the intersection is L2 (non-regular). With L1 = ∅: the union is L2 (non-regular) and the intersection is ∅ (regular). Both outcomes are possible for both operations.

Q2. If L1 and L1 ∪ L2 are regular, must L2 be regular?

No. L1 = Σ*, L2 = { anbn }: L1 ∪ L2 = Σ* is regular but L2 is not.

Q3. If L is not regular, can L̄ (its complement) be regular?

No. If L̄ were regular, then L = complement of L̄ would be regular by closure under complement.

Q4. If L* is regular, must L be regular?

No. Let L = { ap : p is prime }, which is not regular. Every integer k ≥ 2 is a sum of primes (2's and 3's are enough), so L* = { ak : k ≠ 1 } = ε + aaa*, which is regular. (The program confirmed that 1 is the only length missing from L* up to 39.)

Q5. DFAs for L1 and L2 have 3 and 4 states. What is the maximum number of states needed by the product DFA for L1 ∩ L2?

3 × 4 = 12 (some pairs may be unreachable or mergeable, so the minimal DFA can be smaller).

Q6. Prove that { w ∈ {0, 1}* : w has more 0s than 1s } is not regular.

Hint: intersect with 0*1*. If L were regular, L ∩ 0*1* = { 0n1m : n > m } would be regular. That language is also non-regular (it needs to compare n and m without bound; the pumping lemma proves it by pumping down the 0s). Many textbook proofs pump directly instead.

Q7. Is the family of regular languages closed under the operation that maps L to { w : w ∈ L and wR ∈ L }?

Yes. This is L ∩ LR, and regular languages are closed under reversal and intersection.


Summary

  • Regular languages are closed under union, concatenation, star, complement, intersection, difference, symmetric difference, reversal, homomorphism, inverse homomorphism, substitution, quotient, prefix and suffix.

  • They are not closed under infinite union, infinite intersection or taking subsets.

  • Complement needs a complete DFA; swapping accepting states of an NFA is wrong.

  • The product construction runs two DFAs in parallel (at most m × n states); choosing the accepting pairs gives ∩, ∪, − or ⊕.

  • Closure gives a quick way to prove non-regularity: intersect with a regular language (often a*b*) to reach a known non-regular language like anbn.

  • Membership, emptiness, finiteness, universality, subset and equivalence are all decidable for regular languages.

  • The main tool for proving that a language is not regular from scratch is the subject of the next chapter, Pumping Lemma for Regular Languages.