Course contentsShow
← Computer Science
Lesson 1763 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Language Complement and Intersection

Define complement (all strings not in the language) and intersection operations on languages.

Language Complement and Intersection

You'll learn how to define two key set operations—complement and intersection—that combine or contrast formal languages.

What Is Language Complement?

The complement of a language L (written L̄ or Lᶜ) contains all strings that are NOT in L.

Remember from previous lessons that a language is defined over an alphabet Σ, and the set of all possible strings is Σ* (Kleene star). The complement flips membership:

  • L̄ = Σ − L*

If L accepts strings like {a, aa, aaa}, then L̄ accepts everything else over that alphabet: {ε, b, ab, ba, aaaa, ...} (assuming Σ = {a, b}).

Analogy: Think of L as "approved messages." The complement is "all rejected messages."

What Is Language Intersection?

The intersection of two languages L₁ and L₂ (written L₁ ∩ L₂) contains only strings that belong to BOTH languages.

  • L₁ ∩ L₂ = {w | w ∈ L₁ AND w ∈ L₂}

If L₁ = {a, aa, aaa} and L₂ = {aa, aaa, aaaa}, then:

  • L₁ ∩ L₂ = {aa, aaa}

Analogy: Like a Venn diagram overlap—only the shared elements survive.

Why These Matter

Complement and intersection let you express complex constraints:

  • "All strings except palindromes" (complement)
  • "Strings that are both valid JSON and under 100 characters" (intersection)

These operations are fundamental when proving closure properties of language classes (e.g., whether regular languages remain regular under these operations).

Key Takeaway: Complement (L̄) contains all strings NOT in L; intersection (L₁ ∩ L₂) contains only strings in BOTH languages. Both are essential set operations on formal languages.