Union

What is Union?

The union of two languages L₁ and L₂, denoted L₁ ∪ L₂, is the set of all strings that belong to either L₁ or L₂ or both. It combines two languages into one larger language.

Formal Definition

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

A string is in the union if it appears in at least one of the languages.

Simple Analogy

Think of union like combining two groups of people:

• Group A: {Alice, Bob, Charlie}
• Group B: {Bob, David, Eve}
• Union: {Alice, Bob, Charlie, David, Eve}

Notice Bob appears in both groups but is listed only once in the union (sets don’t have duplicates).

Basic Examples

Example 1: Simple Finite Languages

L₁ = {a, b}
L₂ = {b, c}

L₁ ∪ L₂ = {a, b, c}

Note: ‘b’ appears in both, but listed only once in the result.

Example 2: Binary Strings

L₁ = {0, 00, 000}
L₂ = {1, 11, 111}

L₁ ∪ L₂ = {0, 00, 000, 1, 11, 111}

All strings from both languages are included.

Example 3: One Language is Subset

L₁ = {a}
L₂ = {a, b, c}

L₁ ∪ L₂ = {a, b, c} = L₂

When L₁ ⊆ L₂, then L₁ ∪ L₂ = L₂

Example 4: Disjoint Languages

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

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

No common strings, so simply combine all strings.

Example 5: Union with Empty Language

L = {a, b, c}

L ∪ ∅ = {a, b, c} = L

∅ is the identity element for union.

Infinite Language Examples

Example 1: Infinite Binary Languages

L₁ = {0ⁿ | n ≥ 1} = {0, 00, 000, ...}
L₂ = {1ⁿ | n ≥ 1} = {1, 11, 111, ...}

L₁ ∪ L₂ = {strings of only 0's or only 1's}
         = {0, 1, 00, 11, 000, 111, ...}

Example 2: Even and Odd Length Strings

L₁ = {w ∈ {0,1}* | |w| is even}
L₂ = {w ∈ {0,1}* | |w| is odd}

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

Every string is either even or odd length, so union is all strings!

Example 3: Strings Starting or Ending with Specific Symbol

Σ = {0, 1}
L₁ = {w | w starts with 0}
L₂ = {w | w ends with 1}

L₁ ∪ L₂ = {w | w starts with 0 OR ends with 1}

Examples in union: 0, 01, 001, 1, 11, 101, 111, … Not in union: 10, 110 (starts with 1 AND ends with 0)

Properties of Union

1. Commutativity

Order doesn’t matter:

L₁ ∪ L₂ = L₂ ∪ L₁

Example:

L₁ = {a, b}, L₂ = {c, d}
L₁ ∪ L₂ = {a, b, c, d}
L₂ ∪ L₁ = {c, d, a, b} = {a, b, c, d} ✓

2. Associativity

Grouping doesn’t matter:

(L₁ ∪ L₂) ∪ L₃ = L₁ ∪ (L₂ ∪ L₃)

Example:

L₁ = {a}, L₂ = {b}, L₃ = {c}
(L₁ ∪ L₂) ∪ L₃ = {a, b} ∪ {c} = {a, b, c}
L₁ ∪ (L₂ ∪ L₃) = {a} ∪ {b, c} = {a, b, c} ✓

3. Identity Element

Empty language is the identity:

L ∪ ∅ = L

Example:

L = {0, 1}
L ∪ ∅ = {0, 1} = L

4. Idempotent

Union with itself gives same language:

L ∪ L = L

Example:

L = {a, b}
L ∪ L = {a, b} = L

5. Domination

Union with universal language:

L ∪ Σ* = Σ*

Size of Union

For finite languages:

If L₁ and L₂ are disjoint (L₁ ∩ L₂ = ∅):

|L₁ ∪ L₂| = |L₁| + |L₂|

Example:

L₁ = {0, 00}
L₂ = {1, 11}
|L₁| = 2, |L₂| = 2
|L₁ ∪ L₂| = 4 = 2 + 2 ✓

If L₁ and L₂ overlap:

|L₁ ∪ L₂| = |L₁| + |L₂| - |L₁ ∩ L₂|

Example:

L₁ = {a, b, c}
L₂ = {b, c, d}
L₁ ∩ L₂ = {b, c}

|L₁ ∪ L₂| = 3 + 3 - 2 = 4
L₁ ∪ L₂ = {a, b, c, d} (indeed 4 strings) ✓

Union in Regular Expressions

The union operation is represented by | or + in regular expressions.

Examples:

Regex: a|b means {a} ∪ {b} = {a, b}
Regex: (0|1)* means {0, 1}* = all binary strings
Regex: (cat|dog) means {cat, dog}

Closure Property

Important Theorem:

If L₁ and L₂ are regular languages, then L₁ ∪ L₂ is also regular.

This means regular languages are closed under union.

Proof Idea:

If we have DFAs M₁ and M₂ for L₁ and L₂, we can construct a new DFA for L₁ ∪ L₂.

Practical Applications

1. Lexical Analysis

keywords = {if, else, while, for, ...}
identifiers = {variable names}

tokens = keywords ∪ identifiers

2. Pattern Matching

vowels = {a, e, i, o, u}
digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

valid_chars = vowels ∪ digits

3. File Type Recognition

images = {.jpg, .png, .gif}
videos = {.mp4, .avi, .mov}

media = images ∪ videos

4. Error Handling

warnings = {warning messages}
errors = {error messages}

all_issues = warnings ∪ errors

Union vs Other Operations

Important Identities Involving Union

1. L ∪ ∅ = L (identity)
2. L ∪ L = L (idempotent)
3. L ∪ Σ* = Σ* (domination)
4. L ∪ L̄ = Σ* (complement)
5. L₁ ∪ L₂ = L₂ ∪ L₁ (commutative)
6. (L₁ ∪ L₂) ∪ L₃ = L₁ ∪ (L₂ ∪ L₃) (associative)

De Morgan’s Law for Union

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

The complement of a union equals the intersection of complements.

Example:

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

L₁ ∪ L₂ = {0, 1}
(L₁ ∪ L₂)̄ = all strings except 0 and 1 = {ε, 00, 01, 10, 11, ...}

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

Important Exam Points

1. ✓ Union: w ∈ L₁ OR w ∈ L₂
2. ✓ Denoted by ∪ (cup symbol)
3. ✓ Commutative: L₁ ∪ L₂ = L₂ ∪ L₁
4. ✓ Associative: (L₁ ∪ L₂) ∪ L₃ = L₁ ∪ (L₂ ∪ L₃)
5. ✓ Identity: L ∪ ∅ = L
6. ✓ Idempotent: L ∪ L = L
7. ✓ Regular languages closed under union
8. ✓ Size formula: |L₁ ∪ L₂| = |L₁| + |L₂| - |L₁ ∩ L₂|

Common Mistakes to Avoid

❌ Mistake 1: L₁ ∪ L₂ = {w₁w₂ | w₁ ∈ L₁, w₂ ∈ L₂}
✓ Correct: That’s concatenation, not union!

❌ Mistake 2: Union changes the strings
✓ Correct: Union just collects strings as-is

❌ Mistake 3: ∅ ∪ ∅ = ∅ means no strings
✓ Correct: Yes, ∅ ∪ ∅ = ∅ (empty language)

❌ Mistake 4: {a} ∪ {a} = {aa}
✓ Correct: {a} ∪ {a} = {a} (idempotent, not concatenation)

Practice Questions

Q1: Find L₁ ∪ L₂ where L₁ = {a, aa} and L₂ = {b, bb}.

Answer: L₁ ∪ L₂ = {a, aa, b, bb}

Q2: If L₁ = {0ⁿ | n ≥ 0} and L₂ = {1ⁿ | n ≥ 0}, describe L₁ ∪ L₂.

Answer: L₁ ∪ L₂ = {strings containing only 0’s or only 1’s}
= {ε, 0, 1, 00, 11, 000, 111, …}

Q3: What is L ∪ L̄?

Answer: L ∪ L̄ = Σ* (every string is either in L or not in L)

Q4: Is union commutative? Prove with an example.

Answer: Yes. L₁ = {a}, L₂ = {b}
L₁ ∪ L₂ = {a, b} = L₂ ∪ L₁ ✓

Summary

• Union (L₁ ∪ L₂) combines two languages
• Includes strings from either or both languages
• Commutative and associative
• Identity element is ∅ (empty language)
• Regular languages are closed under union
• Used in regular expressions as | operator
• Important in automata theory for combining recognizers

Union is one of the simplest yet most powerful operations in formal language theory!