Closure Properties of Regular Languages

What are Closure Properties?

Closure Property: If we apply an operation to regular language(s), the result is still regular.

Simple Analogy

Think of closure like mathematical operations on integers:

• Integers + Integers = Integer (closed under addition)
• Integers × Integers = Integer (closed under multiplication)
• Integers ÷ Integers = Maybe not integer (NOT closed under division)

Similarly:

• Regular ∪ Regular = Regular (closed under union)
• Regular ∩ Regular = Regular (closed under intersection)
• Regular languages have many closure properties!

Why Important?

1. Build complex languages: Combine simple regular languages
2. Prove regularity: If L = L₁ ∪ L₂ and both regular → L is regular
3. Simplify proofs: Use closure instead of constructing DFA
4. Design algorithms: Operations preserve regularity

Fundamental Closure Properties

1. Union (L₁ ∪ L₂)

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

Definition: L₁ ∪ L₂ = {w | w ∈ L₁ or w ∈ L₂}

Proof Method 1: Regular Expressions

Given:

• L₁ = L(r₁)
• L₂ = L(r₂)

Construct: r = r₁ | r₂

Then: L(r) = L₁ ∪ L₂ ✓

Proof Method 2: NFA Construction

Given: NFA₁ for L₁, NFA₂ for L₂

Construction:

         ε
    ┌────────→ NFA₁ ────────┐
    │                       │ ε
q₀ ─┤                       ├──→ qf
    │                       │ ε
    └────────→ NFA₂ ────────┘
         ε

Steps:

1. Create new start state q₀
2. Create new accept state qf
3. ε-transition from q₀ to both NFA starts
4. ε-transitions from both NFA accepts to qf

Result: NFA accepts L₁ ∪ L₂ ✓

Proof Method 3: Product Construction

Given: DFA₁ = (Q₁, Σ, δ₁, q₁, F₁), DFA₂ = (Q₂, Σ, δ₂, q₂, F₂)

Construct: DFA = (Q₁ × Q₂, Σ, δ, (q₁,q₂), F)

Transition: δ((p,q), a) = (δ₁(p,a), δ₂(q,a))

Accept: F = (F₁ × Q₂) ∪ (Q₁ × F₂)

Accept if: Either component in accept state

State count: |Q₁| × |Q₂|

Example

L₁: Strings ending with ‘0’ L₂: Strings of even length

L₁ ∪ L₂: Strings ending with ‘0’ OR even length

Regex: (0|1)0 | ((0|1)(0|1))

Result: Regular ✓

2. Intersection (L₁ ∩ L₂)

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

Definition: L₁ ∩ L₂ = {w | w ∈ L₁ and w ∈ L₂}

Proof: Product Construction

Given: DFA₁, DFA₂

Construct: DFA = (Q₁ × Q₂, Σ, δ, (q₁,q₂), F₁ × F₂)

Accept: F = F₁ × F₂ (BOTH components accept)

Key difference from union: Accept condition

• Union: F₁ × Q₂ ∪ Q₁ × F₂ (either)
• Intersection: F₁ × F₂ (both)

Alternative Proof: DeMorgan’s Law

Using closure under complement and union:

L₁ ∩ L₂ = ̄(L̄₁ ∪ L̄₂)

Since:
1. L̄₁ and L̄₂ are regular (complement closure)
2. L̄₁ ∪ L̄₂ is regular (union closure)
3. ̄(L̄₁ ∪ L̄₂) is regular (complement closure again)

Example

L₁: Strings ending with ‘1’ L₂: Strings starting with ‘0’

L₁ ∩ L₂: Strings starting with ‘0’ AND ending with ‘1’

Example strings: 01, 001, 011, 0101, …

Regex: 0(0|1)*1

Result: Regular ✓

3. Complement (L̄)

Theorem: If L is regular, then L̄ = Σ* - L is regular.

Definition: L̄ = {w | w ∉ L}

Proof: DFA Complement

Given: DFA M = (Q, Σ, δ, q₀, F) for L

Construct: DFA M’ = (Q, Σ, δ, q₀, Q - F) for L̄

Key: Swap accept and non-accept states

Requirements:

• DFA must be complete (transition for every (state, symbol))
• If incomplete, add dead state first

Why NFA Complement is Harder?

Problem: Simply swapping accept states in NFA doesn’t work!

Reason: NFA accepts if any path accepts

• Original NFA: Some path to accept → accept
• Swapped NFA: Some path to non-accept → NOT necessarily reject all

Solution: Convert NFA → DFA → Complement

Example

L: Binary strings containing “01”

DFA: 3 states, complex transitions

L̄: Binary strings NOT containing “01”

Regex for L̄: 10 (all 1’s followed by all 0’s)

Complement construction: Swap accept states in DFA

Result: Regular ✓

4. Concatenation (L₁L₂)

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

Definition: L₁L₂ = {xy | x ∈ L₁ and y ∈ L₂}

Proof Method 1: Regular Expressions

Given: r₁ for L₁, r₂ for L₂

Construct: r = r₁r₂

Result: L(r) = L₁L₂ ✓

Proof Method 2: NFA Construction

Given: NFA₁ for L₁, NFA₂ for L₂

Construction:

q₀ → NFA₁ → [ε] → NFA₂ → qf

Steps:

1. Remove accept status from NFA₁’s accept states
2. Add ε-transitions from NFA₁’s old accepts to NFA₂’s start
3. NFA₂’s accept states are final accepts

Result: NFA accepts L₁L₂ ✓

Example

L₁: {a, aa, aaa} L₂: {b, bb}

L₁L₂: {ab, abb, aab, aabb, aaab, aaabb}

Regex: a⁺b⁺

Result: Regular ✓

5. Kleene Star (L*)

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

Definition: L* = {ε} ∪ L ∪ LL ∪ LLL ∪ …

Proof Method 1: Regular Expression

Given: r for L

Construct: r*

Result: L(r*) = L* ✓

Proof Method 2: NFA Construction

Given: NFA for L

Construction:

       ┌──────────────── ε ────────────────┐
       ↓                                   │
q₀ → [ε] → NFA(L) → [ε] → qf
 │                          ↑
 └──────────── ε ───────────┘

Steps:

1. Create new start q₀ and accept qf
2. ε from q₀ to old start (for repetitions)
3. ε from old accepts back to old start (loop)
4. ε from q₀ to qf (for ε, zero repetitions)
5. ε from old accepts to qf (stop repetitions)

Result: NFA accepts L* ✓

Example

L: {ab}

L*: {ε, ab, abab, ababab, …}

Regex: (ab)*

Result: Regular ✓

6. Reversal (L^R)

Theorem: If L is regular, then L^R is regular.

Definition: L^R = {w^R | w ∈ L} (reverse each string)

Proof: Reverse DFA/NFA

Given: NFA M = (Q, Σ, δ, q₀, F) for L

Construct: NFA M’ for L^R

Steps:

1. Reverse all transitions: If q →^a p, then add p →^a q
2. Swap start and accepts:
   • Old start → new accept
   • Old accepts → new starts (may need new start with ε-transitions)

Result: NFA accepts L^R ✓

Example

L: Strings ending with “ab”

Regex: (0|1)*ab

L^R: Strings starting with “ba”

Regex: ba(0|1)*

Result: Regular ✓

Advanced Closure Properties

7. Difference (L₁ - L₂)

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

Definition: L₁ - L₂ = {w | w ∈ L₁ and w ∉ L₂}

Proof: Using Intersection and Complement

L₁ - L₂ = L₁ ∩ L̄₂

Since:
1. L̄₂ is regular (complement closure)
2. L₁ ∩ L̄₂ is regular (intersection closure)

Alternative: Product Construction

Accept states: F₁ × (Q₂ - F₂)

Accept if: First accepts, second rejects

Example

L₁: All binary strings L₂: Strings with even length

L₁ - L₂: Strings with odd length

Result: Regular ✓

8. Symmetric Difference (L₁ ⊕ L₂)

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

Definition: L₁ ⊕ L₂ = (L₁ - L₂) ∪ (L₂ - L₁)

Alternative: L₁ ⊕ L₂ = (L₁ ∪ L₂) - (L₁ ∩ L₂)

Proof: Using Difference and Union

L₁ ⊕ L₂ = (L₁ - L₂) ∪ (L₂ - L₁)

Since:
1. L₁ - L₂ and L₂ - L₁ are regular (difference closure)
2. Their union is regular (union closure)

Example

L₁: {a, ab, abc} L₂: {ab, abc, abcd}

L₁ ⊕ L₂: {a, abcd} (in exactly one language)

Result: Regular ✓

9. Homomorphism (h(L))

Theorem: If L is regular and h is a homomorphism, then h(L) is regular.

Definition: h: Σ* → Δ* where h(a) = string for each a ∈ Σ

Extension: h(w) = h(a₁)h(a₂)…h(aₙ) for w = a₁a₂…aₙ

h(L): {h(w) | w ∈ L}

Proof: Modify Regex/NFA

Method 1 (Regex):

• For each symbol a in regex r, replace with h(a)
• Result: Regex for h(L)

Method 2 (NFA):

• For each transition q →^a p, replace with path q →^{h(a)} p
• Result: NFA for h(L)

Example

L: {a, ab, abb} h(a): 01 h(b): 10

h(L): {01, 0110, 011010}

Observation:

• If L regular → h(L) regular
• h(L) has same “structure”, different symbols

Result: Regular ✓

10. Inverse Homomorphism (h⁻¹(L))

Theorem: If L is regular and h is a homomorphism, then h⁻¹(L) is regular.

Definition: h⁻¹(L) = {w | h(w) ∈ L}

Meaning: All strings that map into L

Proof: Construct DFA

Given: DFA M for L, homomorphism h

Construct: DFA M’ for h⁻¹(L)

Key: Simulate M on h(a) for each input symbol a

Transition: δ’(q, a) = δ*(q, h(a)) (process entire h(a))

Example

L: {01, 0101, 010101, …} (alternating 01) h(a): 01 h(b): 10

h⁻¹(L): {a, aaa, aaaaa, …} = a(aa)*

Explanation:

• h(a) = 01 ∈ L ✓
• h(aa) = 0101 ∈ L ✓
• h(b) = 10 ∉ L ✗

Result: Regular ✓

Surprising Fact

Inverse homomorphism is easier to prove than homomorphism!

Why? Can directly construct DFA for h⁻¹(L) from DFA for L.

11. Quotient (L₁/L₂)

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

Definition: L₁/L₂ = {w | ∃x ∈ L₂ such that wx ∈ L₁}

Meaning: All prefixes w such that appending some x ∈ L₂ gives string in L₁

Proof: NFA Construction

Given: DFA M₁ for L₁

Construct: NFA M’ for L₁/L₂

Key Idea:

• State q is accept in M’ if ∃x ∈ L₂ such that δ*(q, x) ∈ F₁
• Use DFA for L₂ to test this

Accept: State q if path from q using some string in L₂ reaches F₁

Example

L₁: {abc, abcd, abd} L₂: {c, d}

L₁/L₂: {ab, abc}

Verification:

• abc ∈ L₁/L₂? Yes, ab·c ∈ L₁
• ab ∈ L₁/L₂? Yes, ab·c ∈ L₁ and ab·d ∈ L₁

Result: Regular ✓

Left Quotient (L₂\L₁)

Definition: L₂\L₁ = {w | ∃x ∈ L₂ such that xw ∈ L₁}

Also regular (similar proof)

12. Substitution (s(L))

Theorem: If L is regular and s(a) is regular for each a, then s(L) is regular.

Definition: s: Σ → 2^Δ* (maps each symbol to a language)

Extension: s(w) = s(a₁)s(a₂)…s(aₙ) for w = a₁a₂…aₙ

s(L): ⋃_{w∈L} s(w)

Proof: Induction + Closure

Base case: Single symbol a → s(a) is regular (given)

Inductive:

• s(w₁w₂) = s(w₁)s(w₂) (concatenation)
• s(w₁|w₂) = s(w₁) ∪ s(w₂) (union)

By closure: Result is regular

Example

L: {a, ab} s(a): {0, 00} s(b): {1, 11}

s(L):

• s(a) = {0, 00}
• s(ab) = s(a)s(b) = {0, 00}{1, 11} = {01, 011, 001, 0011}

s(L): {0, 00, 01, 011, 001, 0011}

Result: Regular ✓

Closure Properties Summary Table

Not Closed Under

Infinite Intersection

Regular languages NOT closed under infinite intersection

Counterexample:

For each n ≥ 1:
  Lₙ = Σ* - {aⁿbⁿ}
  (all strings except aⁿbⁿ)

Each Lₙ is regular (finite complement).

But:
  ⋂_{n=1}^∞ Lₙ = Σ* - {aⁿbⁿ | n ≥ 1}
                = Σ* - {ab, aabb, aaabbb, ...}

This is regular! (doesn't contain any aⁿbⁿ)

Wait... let me reconsider:

Actually:
  ⋂_{n=1}^∞ Lₙ contains all strings EXCEPT all aⁿbⁿ

Better example:
  Lₙ = (a|b)* - {aⁿ}

  ⋂_{n=1}^∞ Lₙ = (a|b)* - {aⁿ | n ≥ 1}
                = (a|b)* - aa*
                = strings NOT of form aa*

Actually this is still regular...

Correct example:
  Let Lₙ = strings where |w| ≠ n
  Each Lₙ is regular

  But ⋂_{n=0}^∞ Lₙ = ∅ (finite strings hit some n)

OK, that works but trivial.

Best example:
  For n ≥ 1, let Lₙ = {w | number of a's ≠ n}
  Each Lₙ regular

  ⋂_{n=1}^∞ Lₙ = strings with infinite a's = ∅

Actually, the statement is more subtle. Regular languages ARE closed under finite intersection, but NOT necessarily under infinite intersection.

Practical Applications

1. Compiler Design

Lexical Analysis:

IDENTIFIER = LETTER(LETTER|DIGIT)*
NUMBER = DIGIT⁺
TOKEN = IDENTIFIER ∪ NUMBER ∪ OPERATOR

Using: Union, concatenation, star

2. Text Processing

Pattern Matching:

Email validation: LOCAL @ DOMAIN
LOCAL = [a-z]⁺  (regular)
DOMAIN = [a-z]+ \. [a-z]+  (regular)
Email = LOCAL concatenate "@" concatenate DOMAIN

Using: Concatenation

3. Network Security

Intrusion Detection:

ATTACK_PATTERN₁ = ...
ATTACK_PATTERN₂ = ...
ALL_ATTACKS = ATTACK_PATTERN₁ ∪ ATTACK_PATTERN₂
SAFE_TRAFFIC = Σ* - ALL_ATTACKS

Using: Union, complement

4. Database Queries

String Pattern Queries:

SELECT * WHERE name LIKE 'A%'
           AND name NOT LIKE '%Z'

Translation:

• A%: Strings starting with ‘A’
• %Z: Strings ending with ‘Z’
• Combined using intersection and complement

5. Bioinformatics

DNA Motif Search:

MOTIF₁ = ATG(A|T|G|C)*TAG
MOTIF₂ = GTG(A|T|G|C)*TAA
BOTH_MOTIFS = MOTIF₁ ∩ MOTIF₂

Using: Intersection, concatenation, star

Proof Techniques Summary

Direct Construction

Build automaton/regex for result:

• Union: Parallel NFAs
• Intersection: Product DFA
• Concatenation: Sequential NFAs

Reduction to Known Closures

Express using operations known to preserve regularity:

• Difference: L₁ - L₂ = L₁ ∩ L̄₂
• Symmetric Difference: (L₁-L₂) ∪ (L₂-L₁)

Induction

Structural induction on regex/automaton:

• Substitution: Induct on structure of words
• Homomorphism: Replace symbols recursively

Important Exam Points

1. ✓ Basic Closure: Union, intersection, complement, concatenation, star
2. ✓ Advanced Closure: Reversal, homomorphism, quotient, substitution
3. ✓ Union Construction: Product DFA with (F₁×Q₂) ∪ (Q₁×F₂)
4. ✓ Intersection Construction: Product DFA with F₁×F₂
5. ✓ Complement Construction: Swap accept/non-accept states in DFA
6. ✓ Difference: L₁ - L₂ = L₁ ∩ L̄₂
7. ✓ Reversal: Reverse transitions, swap start/accept
8. ✓ Homomorphism: Replace symbols with strings
9. ✓ Inverse Homomorphism: Preimages of regular language
10. ✓ NOT closed: Infinite intersection

Common Mistakes to Avoid

✗ Mistake 1: NFA complement by swapping accept states
✓ Correct: Convert to DFA first, then swap

✗ Mistake 2: Thinking all operations preserve regularity
✓ Correct: Most do, but infinite intersection doesn’t

✗ Mistake 3: Product DFA accept states wrong
✓ Correct: Union: (F₁×Q₂)∪(Q₁×F₂), Intersection: F₁×F₂

✗ Mistake 4: Forgetting DFA must be complete for complement
✓ Correct: Add dead state if transitions missing

✗ Mistake 5: Confusing h(L) and h⁻¹(L)
✓ Correct: h(L) applies h to strings in L; h⁻¹(L) finds preimages

✗ Mistake 6: Thinking reversal requires deterministic automaton
✓ Correct: Easier with NFA (DFA reversal may need subset construction)

Practice Questions

Q1: How to construct DFA for L₁ ∩ L₂?

Answer: Product construction with accept states F₁ × F₂.

Q2: Is complement of regular language regular?

Answer: Yes, swap accept/non-accept states in DFA.

Q3: How to prove L₁ - L₂ is regular?

Answer: L₁ - L₂ = L₁ ∩ L̄₂ (use intersection and complement closure).

Q4: What’s h(ab) if h(a)=01, h(b)=10?

Answer: h(ab) = h(a)h(b) = 0110.

Q5: Are regular languages closed under infinite union?

Answer: Not necessarily (depends on the specific languages).

Q6: How to construct NFA for L*?

Answer: Add ε-transitions: new start to old start, old accepts back to old start, new start to new accept, old accepts to new accept.

Q7: What’s the accept condition for product DFA (union)?

Answer: (p,q) accepts if p ∈ F₁ OR q ∈ F₂.

Q8: How to construct NFA for L^R?

Answer: Reverse all transitions, swap start and accept states.

Summary

• Fundamental Closures: Union, intersection, complement, concatenation, star (all proven constructively)
• Advanced Closures: Reversal, difference, homomorphism, inverse homomorphism, quotient, substitution
• Construction Methods:
  • Product DFA (union, intersection)
  • Swap accepts (complement)
  • NFA with ε (concatenation, star)
  • Reverse transitions (reversal)
  • Symbol substitution (homomorphism)
• Key Results:
  • Closed under all standard operations
  • NOT closed under infinite intersection
  • All constructions are algorithmic (can be computed)
• Applications: Compilers, text processing, security, databases, bioinformatics
• Proof Techniques: Direct construction, reduction to known closures, induction

Closure properties make regular languages a robust and well-behaved class - we can freely combine and transform them while preserving regularity!