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.