Language Operations: Union and Concatenation
What you'll learn: How to combine formal languages using union and concatenation to create new languages.
Core Idea
Since languages are just sets of strings, we can apply set operations to them. The two fundamental operations are union and concatenation.
Union of Languages (L₁ ∪ L₂)
The union of two languages contains all strings that belong to either language (or both). It's the standard set union operation.
Example:
- L₁ = {a, ab}
- L₂ = {b, ba}
- L₁ ∪ L₂ = {a, ab, b, ba}
Analogy: Think of union as combining two playlists — the result contains every song from both lists.
Concatenation of Languages (L₁L₂)
The concatenation of two languages creates a new language by taking every string from L₁ and appending every string from L₂. You form all possible combinations.
Example:
- L₁ = {a, ab}
- L₂ = {b, ba}
- L₁L₂ = {ab, aba, abb, abba}
Breaking it down:
- "a" + "b" = "ab"
- "a" + "ba" = "aba"
- "ab" + "b" = "abb"
- "ab" + "ba" = "abba"
Analogy: Concatenation is like combining first names with last names — every first name pairs with every last name to create full names.
Important Note
Unlike string concatenation (which combines two individual strings), language concatenation combines sets of strings, producing a potentially much larger set.
Key Takeaway: Union (L₁ ∪ L₂) merges two languages into one containing strings from either, while concatenation (L₁L₂) creates all possible string combinations by appending each string from L₂ to each string from L₁.