Complement

What is Complement?

The complement of a language L, denoted L̄ (L-bar) or L’ or Lᶜ, is the set of all strings over the alphabet Σ that are not in L. It’s everything in Σ* except what’s in L.

Formal Definition

L̄ = Σ* - L L̄ = {w ∈ Σ* | w ∉ L}

A string is in the complement if and only if it is NOT in the original language.

Simple Analogy

Think of complement like the “opposite” or “negation”:

Universe: All possible strings (Σ*)
Language L: Some specific strings (e.g., strings starting with ‘a’)
Complement L̄: Everything else (strings NOT starting with ‘a’)

It’s like saying “give me everything that is NOT in L”.

Basic Examples

Example 1: Simple Finite Language

Σ = {0, 1}
L = {0, 1}

Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, ...}
L̄ = Σ* - L = {ε, 00, 01, 10, 11, 000, 001, ...}
  = all strings except "0" and "1"
  = strings of length ≠ 1

Example 2: Empty Language

Σ = {a, b}
L = ∅

L̄ = Σ* - ∅ = Σ*
  = {ε, a, b, aa, ab, ba, bb, aaa, ...}

Complement of empty language is the universal language!

Example 3: Universal Language

Σ = {0, 1}
L = Σ* = all strings

L̄ = Σ* - Σ* = ∅

Complement of universal language is the empty language!

Example 4: Language with ε

Σ = {a}
L = {ε}

L̄ = Σ* - {ε} = {a, aa, aaa, aaaa, ...}
  = all non-empty strings
  = Σ⁺

Example 5: Strings Starting with 0

Σ = {0, 1}
L = {w | w starts with 0}
  = {0, 00, 01, 000, 001, 010, 011, ...}

L̄ = {w | w does NOT start with 0}
  = {ε, 1, 10, 11, 100, 101, 110, 111, ...}
  = ε and strings starting with 1

Importance of Alphabet

Critical: The complement depends on the alphabet Σ!

Example:

L = {0, 1}

If Σ = {0, 1}:
L̄ = {ε, 00, 01, 10, 11, 000, ...}

If Σ = {0, 1, 2}:
L̄ = {ε, 2, 00, 01, 02, 10, 11, 12, 20, 21, 22, 000, ...}

Different alphabets give different complements!

Always specify Σ when discussing complement!

Properties of Complement

1. Double Complement

(L̄)̄ = L

The complement of complement gives back the original language.

Example:

L = {0}
L̄ = all strings except "0"
(L̄)̄ = {0} = L ✓

2. Complement of Empty Language

∅̄ = Σ*

3. Complement of Universal Language

(Σ*)̄ = ∅

4. Union and Intersection Relationship

L ∪ L̄ = Σ*
L ∩ L̄ = ∅

Example:

Σ = {0, 1}
L = {0}
L̄ = {ε, 1, 00, 01, 10, 11, ...}

L ∪ L̄ = {0, 1}* = Σ* ✓
L ∩ L̄ = ∅ ✓

5. Complement of Union and Intersection (De Morgan’s Laws)

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

6. Subset Relationship

If L₁ ⊆ L₂, then L̄₂ ⊆ L̄₁

Complement reverses subset relationships!

De Morgan’s Laws for Languages

Very important for exams!

Law 1: Complement of Union

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

Intuition: A string is NOT in (L₁ ∪ L₂) if and only if it’s NOT in L₁ AND NOT in L₂.

Example:

Σ = {0, 1}
L₁ = {0}
L₂ = {1}

L₁ ∪ L₂ = {0, 1}
(L₁ ∪ L₂)̄ = {ε, 00, 01, 10, 11, 000, ...}

L̄₁ = {ε, 1, 00, 01, 10, 11, 000, ...}
L̄₂ = {ε, 0, 00, 01, 10, 11, 000, ...}
L̄₁ ∩ L̄₂ = {ε, 00, 01, 10, 11, 000, ...} ✓

Law 2: Complement of Intersection

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

Intuition: A string is NOT in (L₁ ∩ L₂) if and only if it’s NOT in L₁ OR NOT in L₂.

Example:

Σ = {a, b}
L₁ = {a, aa}
L₂ = {a, ab}

L₁ ∩ L₂ = {a}
(L₁ ∩ L₂)̄ = {ε, b, aa, ab, ba, bb, aaa, ...}

L̄₁ = {ε, b, ab, ba, bb, aaa, aab, ...}
L̄₂ = {ε, b, aa, ba, bb, aaa, aab, ...}
L̄₁ ∪ L̄₂ = {ε, b, aa, ab, ba, bb, aaa, ...} ✓

Complement of Infinite Languages

Example 1: Even Length Strings

Σ = {0, 1}
L = {w | |w| is even}
  = {ε, 00, 01, 10, 11, 0000, ...}

L̄ = {w | |w| is odd}
  = {0, 1, 000, 001, 010, 011, 100, ...}

Example 2: Strings Containing Substring

Σ = {0, 1}
L = {w | w contains "01" as substring}
  = {01, 001, 010, 101, 011, 0011, ...}

L̄ = {w | w does NOT contain "01"}
  = {ε, 0, 1, 00, 11, 000, 111, 0000, 1111, 1110, ...}
  = strings that are all 0's, all 1's, or end with 1's after 0's

Example 3: Equal Number of a’s and b’s

Σ = {a, b}
L = {w | #a(w) = #b(w)}
  = {ε, ab, ba, aabb, abab, abba, baab, baba, bbaa, ...}

L̄ = {w | #a(w) ≠ #b(w)}
  = {a, b, aa, bb, aaa, abb, bbb, aaaa, ...}

Complement in Regular Languages

Important Theorem:

If L is a regular language, then L̄ is also regular.

Regular languages are closed under complement.

How to Find Complement of DFA

Start with DFA M for language L
Swap accepting and non-accepting states
The resulting DFA accepts L̄

Example:

DFA for L (strings ending in '0'):
- States: {q₀, q₁}
- Start: q₀
- Accept: {q₁}
- Transitions:
  - q₀ --0--> q₁
  - q₀ --1--> q₀
  - q₁ --0--> q₁
  - q₁ --1--> q₀

DFA for L̄ (strings NOT ending in '0'):
- Everything same, but
- Accept: {q₀} (swap accepting states)

Practical Applications

1. Input Validation

valid_emails = {valid email patterns}
invalid_emails = valid_emails̄

2. Error Detection

correct_programs = {syntactically correct programs}
errors = correct_programs̄

3. Security Filters

allowed_requests = {safe requests}
blocked_requests = allowed_requests̄

4. Pattern Exclusion

L = {strings containing profanity}
L̄ = {clean strings}

Relationship with Other Operations

Complement and Union

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

Complement and Intersection

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

Complement and Difference

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

Difference can be expressed using complement!

Example:

L₁ = {0, 1, 00}
L₂ = {0, 1}

L₁ - L₂ = {00}
L̄₂ = {ε, 00, 01, 10, 11, ...}
L₁ ∩ L̄₂ = {00} ✓

Size of Complement

For finite universe:

|L̄| = |Σ*| - |L|

But since Σ* is infinite, both L and L̄ are typically infinite.

Special Cases:

If L is finite:

L̄ is infinite (assuming Σ ≠ ∅)

If L is infinite:

L̄ can be finite or infinite

Example (L̄ is finite):

Σ = {0}
L = {0}* = {ε, 0, 00, 000, ...}
L̄ = ∅ (finite - size 0!)

Complement NOT Closed For Some Classes

While regular languages are closed under complement:

Context-Free Languages: NOT closed under complement
Deterministic Context-Free Languages: Closed under complement
Recursively Enumerable Languages: NOT closed under complement
Recursive Languages: Closed under complement

Important Identities

(L̄)̄ = L (involution)
∅̄ = Σ* (complement of empty)
(Σ*)̄ = ∅ (complement of universal)
L ∪ L̄ = Σ* (union with complement)
L ∩ L̄ = ∅ (intersection with complement)
(L₁ ∪ L₂)̄ = L̄₁ ∩ L̄₂ (De Morgan 1)
(L₁ ∩ L₂)̄ = L̄₁ ∪ L̄₂ (De Morgan 2)
L₁ - L₂ = L₁ ∩ L̄₂ (difference using complement)
If L₁ ⊆ L₂, then L̄₂ ⊆ L̄₁ (subset reversal)

Important Exam Points

✓ Complement: L̄ = Σ* - L (all strings NOT in L)
✓ Depends on alphabet: Always specify Σ
✓ (L̄)̄ = L (double complement)
✓ ∅̄ = Σ* and (Σ*)̄ = ∅
✓ L ∪ L̄ = Σ* (union is universal)
✓ L ∩ L̄ = ∅ (intersection is empty)
✓ De Morgan’s Laws: (L₁ ∪ L₂)̄ = L̄₁ ∩ L̄₂
✓ Regular languages closed under complement
✓ DFA complement: swap accepting/non-accepting states
✓ L₁ - L₂ = L₁ ∩ L̄₂

Common Mistakes to Avoid

❌ Mistake 1: Forgetting to specify Σ
✓ Correct: Complement depends on the alphabet

❌ Mistake 2: ∅̄ = ∅
✓ Correct: ∅̄ = Σ*

❌ Mistake 3: (L₁ ∪ L₂)̄ = L̄₁ ∪ L̄₂
✓ Correct: (L₁ ∪ L₂)̄ = L̄₁ ∩ L̄₂ (De Morgan’s Law)

❌ Mistake 4: L̄ is always infinite
✓ Correct: L̄ can be finite (e.g., if L = Σ* - {finite set})

❌ Mistake 5: Complement changes the strings
✓ Correct: Complement just selects different strings from Σ*

❌ Mistake 6: (L̄)̄ ≠ L
✓ Correct: (L̄)̄ = L always

Practice Questions

Q1: If Σ = {0, 1} and L = {ε}, what is L̄?

Answer: L̄ = {0, 1}⁺ = all non-empty strings

Q2: What is ∅̄?

Answer: ∅̄ = Σ* (universal language)

Q3: If L = {w | |w| is even}, describe L̄.

Answer: L̄ = {w | |w| is odd}

Q4: Simplify (L̄)̄.

Answer: (L̄)̄ = L

Q5: What is L ∩ L̄?

Answer: L ∩ L̄ = ∅ (empty language)

Q6: Express L₁ - L₂ using complement.

Answer: L₁ - L₂ = L₁ ∩ L̄₂

Q7: Apply De Morgan’s Law to (L₁ ∩ L₂)̄.

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

Q8: Is the complement of a regular language regular?

Answer: Yes, regular languages are closed under complement.

Summary

Complement (L̄) contains all strings in Σ* that are NOT in L
Depends on alphabet Σ - must be specified
Double complement: (L̄)̄ = L
Special cases: ∅̄ = Σ*, (Σ*)̄ = ∅
Union/Intersection: L ∪ L̄ = Σ*, L ∩ L̄ = ∅
De Morgan’s Laws: (L₁ ∪ L₂)̄ = L̄₁ ∩ L̄₂
Regular languages closed under complement
DFA complement: Swap accepting and non-accepting states
Used for negation, exclusion, and error detection

Complement is a fundamental operation for expressing “everything except” patterns and is essential for proving language properties!

Complement

What is Complement?

Formal Definition

Simple Analogy

Basic Examples

Example 1: Simple Finite Language

Example 2: Empty Language

Example 3: Universal Language

Example 4: Language with ε

Example 5: Strings Starting with 0

Importance of Alphabet

Example:

Properties of Complement

1. Double Complement

2. Complement of Empty Language

3. Complement of Universal Language

4. Union and Intersection Relationship

5. Complement of Union and Intersection (De Morgan’s Laws)

6. Subset Relationship

De Morgan’s Laws for Languages

Law 1: Complement of Union

Law 2: Complement of Intersection

Complement of Infinite Languages

Example 1: Even Length Strings

Example 2: Strings Containing Substring

Example 3: Equal Number of a’s and b’s

Complement in Regular Languages

How to Find Complement of DFA

Practical Applications

1. Input Validation

2. Error Detection

3. Security Filters

4. Pattern Exclusion

Relationship with Other Operations

Complement and Union

Complement and Intersection

Complement and Difference

Size of Complement

Special Cases:

Complement NOT Closed For Some Classes

Important Identities

Important Exam Points

Common Mistakes to Avoid

Practice Questions

Summary

Install Notes App