Concatenation

What is Concatenation?

The concatenation of two languages L₁ and L₂, denoted L₁ · L₂ or simply L₁L₂, creates a new language by joining every string from L₁ with every string from L₂. It’s like creating all possible combinations by placing strings from L₂ after strings from L₁.

Formal Definition

L₁ · L₂ = {w₁w₂ | w₁ ∈ L₁ and w₂ ∈ L₂}

Every string in the result is formed by concatenating a string from L₁ followed by a string from L₂.

Simple Analogy

Think of concatenation like creating full names:

• First Names (L₁): {John, Mary}
• Last Names (L₂): {Smith, Jones}
• Full Names (L₁ · L₂): {JohnSmith, JohnJones, MarySmith, MaryJones}

Every first name is paired with every last name.

Basic Examples

Example 1: Simple Concatenation

L₁ = {a, b}
L₂ = {0, 1}

L₁ · L₂ = {a0, a1, b0, b1}

Process:

• a with 0 → a0
• a with 1 → a1
• b with 0 → b0
• b with 1 → b1

Example 2: Single Element Languages

L₁ = {cat}
L₂ = {dog}

L₁ · L₂ = {catdog}

Example 3: Different Sizes

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

L₁ · L₂ = {000, 0000}

Example 4: With Empty String

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

L₁ · L₂ = {aε, ac, bε, bc}
         = {a, ac, b, bc}

Note: aε = a (concatenating with ε doesn’t change the string)

Example 5: Concatenation with {ε}

L = {0, 1}

L · {ε} = {0ε, 1ε} = {0, 1} = L

{ε} is the identity element for concatenation!

Example 6: Concatenation with ∅

L = {a, b, c}

L · ∅ = ∅

Since ∅ has no strings, there’s nothing to concatenate with. Result is empty.

NOT Commutative!

Very Important: Concatenation is NOT commutative.

Example Showing Non-Commutativity:

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

L₁ · L₂ = {ab}
L₂ · L₁ = {ba}

{ab} ≠ {ba}
Therefore, L₁ · L₂ ≠ L₂ · L₁

Another Example:

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

L₁ · L₂ = {000, 100}
L₂ · L₁ = {000, 001}

Different results!

Properties of Concatenation

1. Associativity ✓

Grouping doesn’t matter:

(L₁ · L₂) · L₃ = L₁ · (L₂ · L₃)

Example:

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

(L₁ · L₂) · L₃ = {ab} · {c} = {abc}
L₁ · (L₂ · L₃) = {a} · {bc} = {abc} ✓

2. Identity Element

The language {ε} is the identity:

L · {ε} = {ε} · L = L

Example:

L = {cat, dog}
L · {ε} = {catε, dogε} = {cat, dog} = L ✓

3. Absorbing Element

The empty language ∅ absorbs everything:

L · ∅ = ∅ · L = ∅

Example:

L = {a, b, c}
L · ∅ = ∅ (no strings to concatenate with)

4. NOT Commutative ✗

L₁ · L₂ ≠ L₂ · L₁ (in general)

5. NOT Idempotent

L · L ≠ L (in general)

Example:

L = {a}
L · L = {aa} ≠ {a}

Size of Concatenation

For finite languages (without ε):

|L₁ · L₂| ≤ |L₁| × |L₂|

Equality holds when all resulting strings are distinct.

Example with Equality:

L₁ = {a, b}
L₂ = {0, 1}

|L₁| = 2, |L₂| = 2
|L₁ · L₂| = 4 = 2 × 2 ✓

L₁ · L₂ = {a0, a1, b0, b1} (all distinct)

Example with Inequality:

L₁ = {a, aa}
L₂ = {ε, a}

|L₁| = 2, |L₂| = 2
L₁ · L₂ = {a, aa, aa, aaa} = {a, aa, aaa}
|L₁ · L₂| = 3 < 4 (duplicates removed)

String Length in Concatenation

For strings w₁ ∈ L₁ and w₂ ∈ L₂:

|w₁ · w₂| = |w₁| + |w₂|

Example:

w₁ = "abc" (length 3)
w₂ = "de" (length 2)
w₁ · w₂ = "abcde" (length 5 = 3 + 2) ✓

Powers of Languages

Concatenating a language with itself multiple times:

Definition:

L⁰ = {ε} (by convention)
L¹ = L
L² = L · L
L³ = L · L · L
Lⁿ = L · L · ... · L (n times)

Examples:

Example 1:

L = {a, b}

L⁰ = {ε}
L¹ = {a, b}
L² = {aa, ab, ba, bb}
L³ = {aaa, aab, aba, abb, baa, bab, bba, bbb}

Example 2:

L = {0}

L⁰ = {ε}
L¹ = {0}
L² = {00}
L³ = {000}
Lⁿ = {0ⁿ} (n zeros)

Example 3:

L = {ab}

L² = {abab}
L³ = {ababab}
Lⁿ = {(ab)ⁿ}

Infinite Language Examples

Example 1: All Strings of 0’s followed by 1’s

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

L₁ · L₂ = {0ⁿ1ᵐ | n, m ≥ 0}
         = {ε, 0, 1, 01, 00, 11, 001, 011, 0011, ...}

Example 2: Strings Starting and Ending with Specific Symbols

L₁ = {strings starting with 0}
L₂ = {strings ending with 1}

L₁ · L₂ = {strings that have 0 followed eventually by 1}

Concatenation in Regular Expressions

In regular expressions, concatenation is implicit (no operator needed):

Examples:

Regex: ab means {a} · {b} = {ab}
Regex: abc means {a} · {b} · {c} = {abc}
Regex: (a|b)(0|1) means ({a}∪{b}) · ({0}∪{1}) = {a0, a1, b0, b1}

Closure Property

Important Theorem:

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

Regular languages are closed under concatenation.

Practical Applications

1. String Formatting

firstName = {"John", "Mary"}
lastName = {"Smith", "Jones"}

fullName = firstName · " " · lastName

2. Token Sequences

keyword = {"if", "while", "for"}
identifier = {variable names}

statement = keyword · " " · identifier

3. URL Construction

protocol = {"http://", "https://"}
domain = {"google.com", "github.com"}

URL = protocol · domain

4. File Paths

directory = {"/home", "/usr"}
subdir = {"/bin", "/lib"}

path = directory · subdir

Concatenation vs Union

Important Identities

1. L · {ε} = {ε} · L = L (identity)
2. L · ∅ = ∅ · L = ∅ (absorbing)
3. (L₁ · L₂) · L₃ = L₁ · (L₂ · L₃) (associative)
4. L₁ · (L₂ ∪ L₃) = (L₁ · L₂) ∪ (L₁ · L₃) (distributive over union)
5. (L₁ ∪ L₂) · L₃ = (L₁ · L₃) ∪ (L₂ · L₃) (distributive)
6. Lⁿ · Lᵐ = Lⁿ⁺ᵐ (exponent addition)
7. (Lⁿ)ᵐ = Lⁿᵐ (exponent multiplication)

Important Exam Points

1. ✓ Concatenation: L₁ · L₂ = {w₁w₂ | w₁ ∈ L₁, w₂ ∈ L₂}
2. ✓ NOT commutative: L₁ · L₂ ≠ L₂ · L₁ (usually)
3. ✓ IS associative: (L₁ · L₂) · L₃ = L₁ · (L₂ · L₃)
4. ✓ Identity: {ε} (not ∅!)
5. ✓ Absorbing element: ∅
6. ✓ Lⁿ means L concatenated n times
7. ✓ L⁰ = {ε} by convention
8. ✓ Regular languages closed under concatenation
9. ✓ |w₁ · w₂| = |w₁| + |w₂|

Common Mistakes to Avoid

❌ Mistake 1: L₁ · L₂ = L₂ · L₁
✓ Correct: Concatenation is NOT commutative

❌ Mistake 2: Identity for concatenation is ∅
✓ Correct: Identity is {ε}

❌ Mistake 3: L · ∅ = L
✓ Correct: L · ∅ = ∅ (absorbing)

❌ Mistake 4: |L₁ · L₂| = |L₁| + |L₂|
✓ Correct: |L₁ · L₂| ≤ |L₁| × |L₂|

❌ Mistake 5: {a, b} · {c} = {a, b, c}
✓ Correct: {a, b} · {c} = {ac, bc}

❌ Mistake 6: L² = L
✓ Correct: L² = L · L (different, except for special cases)

Practice Questions

Q1: Find L₁ · L₂ where L₁ = {a, ab} and L₂ = {b, c}.

Answer: L₁ · L₂ = {ab, ac, abb, abc}

Q2: What is {ε} · {a, b}?

Answer: {ε} · {a, b} = {a, b}

Q3: If L = {0, 1}, find L².

Answer: L² = {00, 01, 10, 11}

Q4: Is {ab} · {cd} = {cd} · {ab}?

Answer: No. {ab} · {cd} = {abcd}, but {cd} · {ab} = {cdab}

Q5: What is L · ∅?

Answer: L · ∅ = ∅ (for any language L)

Q6: If L = {a}, what is L³?

Answer: L³ = {aaa}

Summary

• Concatenation (L₁ · L₂) joins strings from two languages
• Creates {w₁w₂} for all combinations of strings
• NOT commutative: order matters!
• IS associative: grouping doesn’t matter
• Identity: {ε} (empty string language)
• Absorbing: ∅ (empty language)
• Lⁿ: Language concatenated n times with itself
• Regular languages closed under concatenation
• Fundamental operation for building complex languages

Concatenation is essential for constructing patterns and is the basis for many regular expression operations!