Closure Properties of Regular Languages

Building With Lego Bricks

A child with ten distinct Lego pieces can build far more than ten structures. The power is in combination connecting existing pieces according to specific rules.

Regular languages work the same way. Once you know a handful of regular languages, closure properties let you construct an unlimited number of new ones. And crucially, each constructed language is guaranteed to be regular no separate DFA proof needed.

Closure properties also work as demolition tools. If a language would have to be regular as a consequence of closure (because it is built from regular languages using closure preserving operations) but you already know it is not regular then one of your assumptions must be wrong. This indirect reasoning can prove non regularity without ever explicitly constructing a pumping lemma argument.

These properties are not just theoretical conveniences. They are the mathematical foundation of how lexical analyzers in compilers are built: combine simple token recognizers using union and concatenation, and the result is still a DFA recognizable language.

Closure Under Union

Theorem: If L₁ and L₂ are regular, then L₁ ∪ L₂ is regular.

Construction: Given DFA M₁ = (Q₁, Σ, δ₁, q₁, F₁) recognizing L₁ and DFA M₂ = (Q₂, Σ, δ₂, q₂, F₂) recognizing L₂, build the product construction:

• States: Q₁ × Q₂ = {(q, r) | q ∈ Q₁, r ∈ Q₂}
• Start state: (q₁, q₂) simulate both DFAs simultaneously
• Transition: δ((q, r), a) = (δ₁(q, a), δ₂(r, a))
• Accept states: {(q, r) | q ∈ F₁ or r ∈ F₂}

Alternative (NFA construction): Add a new start state with ε-transitions to the start states of both NFAs. Accept if either NFA reaches its accept state.

Why it works: Each pair state (q, r) records the current state of both DFAs. The combined machine accepts if either DFA would accept.

Example: L₁ = strings ending in "0", L₂ = strings beginning with "1". L₁ ∪ L₂ = strings ending in "0" OR beginning with "1". The union DFA's state space is |Q₁| × |Q₂| manageable for small component machines.

Closure Under Concatenation

Theorem: If L₁ and L₂ are regular, then L₁ · L₂ is regular.

Construction (NFA): Connect the two NFAs with ε-transitions from every accept state of NFA₁ to the start state of NFA₂.

Why it works: The NFA non deterministically "guesses" where L₁ ends and L₂ begins. If any split of the input string puts the prefix in L₁ and the suffix in L₂, the NFA accepts.

Closure Under Kleene Star

Theorem: If L is regular, then L* is regular.

Construction (NFA):

1. Add a new start state q_new (also an accept state L* includes ε)
2. Add ε-transitions from q_new to the original start state
3. Add ε-transitions from each original accept state back to the original start state

This allows the NFA to "loop" through L as many times as needed.

Closure Under Complement

Theorem: If L is regular over alphabet Σ, then L̄ = Σ* − L is regular.

Construction (DFA): Given DFA M recognizing L, build DFA M' recognizing L̄ by swapping accept and non accept states:

• F' = Q − F (every non accept state becomes an accept state, and vice versa)

Critical requirement: M must be a complete DFA (every state has a transition on every input symbol). If there are implicit dead states (missing transitions), they must be made explicit before swapping otherwise a dead state (which was implicitly non accepting) would incorrectly become accepting in M'.

Why complement is useful for proofs:

• To prove L is not regular: assume it is, then construct L̄ (also regular by closure), then construct L̄ ∩ (some simple regular L₂), and show the result must be non regular contradiction.
• To build systems: a filter that rejects invalid inputs is the complement of the filter that accepts valid ones.

Closure Under Intersection

Theorem: If L₁ and L₂ are regular, then L₁ ∩ L₂ is regular.

Two constructions:

Via complement and union (De Morgan's Law):

L₁ ∩ L₂ = complement(complement(L₁) ∪ complement(L₂)) Since regular languages are closed under complement and union, they are also closed under intersection.

Via product construction (direct): Same construction as union, but accept states are pairs where both components are in accept states:

Accept states: {(q, r) | q ∈ F₁ and r ∈ F₂}

Closure Under Difference

Theorem: If L₁ and L₂ are regular, then L₁ − L₂ is regular.

Construction:

L₁ − L₂ = L₁ ∩ complement(L₂)

Since regular languages are closed under intersection and complement, they are closed under difference.

Practical meaning: L₁ − L₂ contains strings that are in L₁ but not in L₂. Useful for building "except" filters.

Closure Under Reversal

Theorem: If L is regular, then L^R (the language of reversed strings) is regular.

Construction (NFA from DFA):

1. Reverse all transitions (edges in the diagram flip direction)
2. The old accept states become new start states (add a new start state with ε-transitions to all old accept states)
3. The old start state becomes the new accept state

Example: If L accepts strings ending in "01", then L^R accepts strings beginning with "10" (the reversed pattern "10").

Complete Reference Table

Decision Properties

Beyond closure, there are important algorithmic questions about regular languages problems with yes/no answers that can be solved by algorithms (unlike the Halting Problem).

Emptiness: Is L(M) = ∅?

• Algorithm: does any accept state have a path from the start state?
• Method: BFS/DFS from start state; if no accept state is reachable, L = ∅
• Time: O(|Q| + |transitions|)

Finiteness: Is L(M) finite?

• Algorithm: is there a cycle in the DFA on any path from start to accept?
• Method: detect cycles using DFS; if yes and the cycle is "useful" (reaches an accept state), L is infinite
• Finite regular languages are exactly those whose minimal DFA has no cycles between start and accept states

Equality: Is L(M₁) = L(M₂)?

• Algorithm: minimize both DFAs using Hopcroft's algorithm; check isomorphism
• Alternative: check L(M₁) △ L(M₂) = ∅ (symmetric difference is empty)
• Note: L(M₁) △ L(M₂) = (L₁ − L₂) ∪ (L₂ − L₁) closed under our operations, so computable

Membership: Is w ∈ L(M)?

• Algorithm: simply run M on w
• Time: O(|w|)

Using Closure to Prove Non Regularity

Closure properties can sometimes replace the Pumping Lemma:

Example: Prove that L = {0^i 1^j | i ≠ j} is not regular.

Proof using closure: Assume L is regular. Then:

• L₁ = {0^i 1^j | i ≤ j} (strings where count of 0s ≤ count of 1s)
  • L₁ = L ∩ {0^i 1^j | i ≤ j}... but we need to show {0^i 1^j | i ≤ j} is regular first.

Alternative approach: Assume L is regular. Then complement(L) = {0^n 1^n | n ≥ 0} ∪ {strings not of the form 01} must also be regular (closed under complement). But {0^n 1^n} is not regular (by Pumping Lemma, Lesson 7). The strings of the form 01 form a regular language, and intersecting complement(L) with 01 gives {0^n 1^n} regular by closure. Contradiction. Therefore L is not regular. □

This argument used closure under complement and intersection to derive a contradiction from the Pumping Lemma result.

Application: Lexical Analysis in Compilers

A compiler's lexer (lexical analyzer) must recognize multiple token types simultaneously: keywords, identifiers, integer literals, string literals, operators, whitespace.

Each token type is defined by a regular expression:

• Keyword: if | else | while | for | return | ...
• Identifier: [a zA Z_][a zA Z0-9_]*
• Integer literal: [0-9]+
• Whitespace: [ \t\n\r]+

The lexer recognizes their union all tokens combined. By closure under union, the combined language is also regular. A single DFA (constructed by the product construction, then minimized) can recognize all tokens in one pass.

Lexer generators (flex, re2c, ANTLR) automate this process: they take the regex rules, apply closure constructions, convert to a DFA, minimize it, and output the DFA as a C/C++/Java lookup table.

The Power of Knowing Limits

Closure properties give you two superpowers:

Building: Combine simple regular languages into complex ones. If you know the components are regular and you use only closure preserving operations, the result is regular no new DFA proof required.

Proving limits: If a language cannot be built from known regular languages using closure operations or if its existence would imply the existence of a known non regular language then it is not regular.

Together with the Pumping Lemma, closure properties give you a complete toolkit for determining where a language falls in the Chomsky hierarchy at least for the question of regularity.

The next chapters of the Theory of Computation course move upward in the hierarchy: to context free grammars and pushdown automata, the models that capture the syntax of programming languages. There, you will meet the Context Free Pumping Lemma, and learn why balanced parentheses trivially recognized by humans require a fundamentally more powerful machine.