Kleene Star

What is Kleene Star?

The Kleene Star (or Kleene Closure) of a language L, denoted L*, is the set of all possible strings that can be formed by concatenating zero or more strings from L. It includes the empty string ε and all possible repetitions and combinations of strings from L.

Formal Definition

L* = L⁰ ∪ L¹ ∪ L² ∪ L³ ∪ …

Where:

  • L⁰ = {ε}
  • L¹ = L
  • L² = L · L
  • L³ = L · L · L
  • Lⁿ = L concatenated n times

Alternatively:

L* = {w₁w₂w₃…wₙ | n ≥ 0 and each wᵢ ∈ L}

Simple Analogy

Think of Kleene Star like a “repeat any number of times” operation:

  • If L = {a}, then L* = “use ‘a’ zero or more times”
  • Result: {ε, a, aa, aaa, aaaa, …}

It’s like having unlimited copies of strings from L and being able to use any number of them (including zero).

Basic Examples

Example 1: Single Symbol

L = {a}

L* = {ε, a, aa, aaa, aaaa, ...}
   = {aⁿ | n ≥ 0}

All possible repetitions of ‘a’, including none (ε).

Example 2: Two Symbols

L = {0, 1}

L* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, ...}
   = {all possible binary strings}
   = Σ* where Σ = {0, 1}

Example 3: Multi-Character String

L = {ab}

L* = {ε, ab, abab, ababab, abababab, ...}
   = {(ab)ⁿ | n ≥ 0}

Example 4: Multiple Strings

L = {a, b}

L* = {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, ...}
   = all strings over {a, b}

Example 5: Language with ε

L = {ε, a}

L* = {ε, a, aa, aaa, aaaa, ...}
   = {aⁿ | n ≥ 0}

Note: L* = {a}* when ε is in L

Kleene Plus (L⁺)

Kleene Plus is similar to Kleene Star but excludes the empty string:

L⁺ = L¹ ∪ L² ∪ L³ ∪ … L⁺ = L* - {ε} L⁺ = L · L*

Examples:

L = {a}

L* = {ε, a, aa, aaa, ...}
L⁺ = {a, aa, aaa, aaaa, ...} (no ε)
L = {0, 1}

L* = {ε, 0, 1, 00, 01, 10, 11, ...}
L⁺ = {0, 1, 00, 01, 10, 11, ...} (no ε)

Relationship:

L* = L⁺ ∪ {ε}
L⁺ = L · L*

Step-by-Step Construction

Let’s build L* step by step for L = {a, b}:

L⁰ = {ε}

L¹ = L = {a, b}

L² = L · L = {aa, ab, ba, bb}

L³ = L · L · L = {aaa, aab, aba, abb, baa, bab, bba, bbb}

L* = L⁰ ∪ L¹ ∪ L² ∪ L³ ∪ …

= {ε} ∪ {a, b} ∪ {aa, ab, ba, bb} ∪ {aaa, aab, ...} ∪ ...
= {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, ...}

Special Cases

Case 1: Empty Language

L = ∅

L⁰ = {ε}
L¹ = ∅
L² = ∅ · ∅ = ∅
...

∅* = {ε}

Important: The Kleene Star of empty language is {ε}, not ∅!

Case 2: Language Containing Only ε

L = {ε}

L⁰ = {ε}
L¹ = {ε}
L² = {ε} · {ε} = {ε}
...

{ε}* = {ε}

Case 3: Universal Language

L = Σ*

(Σ*)* = Σ*

Kleene Star is idempotent on Σ*.

Case 4: Single Symbol

L = {a}

L* = {ε, a, aa, aaa, aaaa, ...} = {aⁿ | n ≥ 0}

Properties of Kleene Star

1. Always Contains ε

ε ∈ L* for any language L

Example:

L = {0, 1}
ε ∈ {0, 1}* ✓ (from L⁰)

2. L ⊆ L*

The original language is always a subset:

L ⊆ L*

Example:

L = {a, b}
{a, b} ⊆ {ε, a, b, aa, ab, ba, bb, ...} ✓

3. Idempotent Property

(L*)* = L*

Proof Idea: L* already contains all possible concatenations, so repeating the operation doesn’t add anything new.

4. Union Property

(L₁ ∪ L₂)* = (L₁* · L₂*)* = (L₁ ∪ L₂)*

5. ∅ is Special

∅* = {ε}
{ε}* = {ε}

6. Concatenation with L*

L · L* = L* · L = L⁺

7. Monotonicity

If L₁ ⊆ L₂, then L₁* ⊆ L₂*

Size of L*

For any non-empty language L:

|L*| = ∞ (infinite)

Exception: Only when L = ∅ or L = {ε}, then |L*| = 1

Why is L* Infinite?

If L contains at least one non-empty string w:

  • L⁰ = {ε}
  • L¹ contains w
  • L² contains ww
  • L³ contains www
  • …

Since we can repeat infinitely, L* is infinite.

Infinite Language Examples

Example 1: All Binary Strings

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

L* = Σ* = all binary strings
   = {ε, 0, 1, 00, 01, 10, 11, 000, ...}

Example 2: Strings of a’s followed by b’s

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

L₁* · L₂* = {aⁿbᵐ | n, m ≥ 0}
          = {ε, a, b, ab, aa, bb, aab, abb, aabb, ...}

Example 3: Even-Length Strings

L = {aa, bb, ab, ba}

L* = all strings formed by concatenating these pairs
   = all even-length strings over {a, b}

Example 4: Palindrome Building Blocks

L = {aba, bab}

L* = {ε, aba, bab, abaaba, ababab, bababa, babbab, ...}

Kleene Star in Regular Expressions

In regular expressions, * denotes Kleene Star:

Examples:

Regex: a* means {ε, a, aa, aaa, ...}
Regex: (ab)* means {ε, ab, abab, ababab, ...}
Regex: (0|1)* means all binary strings
Regex: [a-z]* means all lowercase strings (including ε)

Closure Property

Important Theorem:

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

Regular languages are closed under Kleene Star.

Proof Idea:

If we have a DFA/NFA for L, we can construct an NFA for L* by:

  1. Adding a new start state that is also accepting (for ε)
  2. Adding ε-transitions from accepting states back to the start

Practical Applications

1. Pattern Matching

Pattern: a* matches "", "a", "aa", "aaa", ...
Pattern: [0-9]* matches any sequence of digits

2. Lexical Analysis

identifier = letter · (letter | digit)*
           = letter followed by zero or more letters/digits

3. Protocol Sequences

handshake* = (SYN · ACK)*
           = zero or more handshake sequences

4. Repeat Constructs

HTML: <li>*  means zero or more list items
SQL: WHERE clause (AND condition)*

Combining Kleene Star with Other Operations

Example 1: Union and Star

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

(L₁ ∪ L₂)* = {a, b}* = all strings over {a, b}

Example 2: Concatenation and Star

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

L₁* · L₂* = {0}* · {1}* = {0ⁿ1ᵐ | n, m ≥ 0}
          = strings of 0's followed by 1's

Example 3: Nested Stars

L = {a}

(L*)* = ({ε, a, aa, aaa, ...})* = {ε, a, aa, aaa, ...} = L*

Idempotent property!

Example 4: Star and Complement

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

L* = {ε, 0, 00, 000, ...}
L̄* = complement of L*
   = strings containing at least one '1'

Important Identities

  1. ∅* = {ε} (special case)
  2. {ε}* = {ε} (idempotent for {ε})
  3. (L) = L*** (idempotent)
  4. L⁺ = L · L* (Kleene Plus)
  5. L* = L⁺ ∪ {ε} (relationship)
  6. L ⊆ L* (language is subset of its star)
  7. ε ∈ L* (always contains ε)
  8. Σ · Σ = Σ*** (concatenation with universal)
  9. (Σ) = Σ*** (idempotent for universal)
  10. L · L = L · L = L⁺** (concatenation property)

Important Exam Points

  1. ✓ Kleene Star: L* = all concatenations of 0 or more strings from L
  2. ✓ Always includes ε: ε ∈ L* (from L⁰)
  3. ✓ L* is infinite (except for ∅ and {ε})
  4. ✓ ∅* = {ε} (not ∅!)
  5. ✓ {ε}* = {ε}
  6. ✓ (L) = L*** (idempotent)
  7. ✓ L⁺ = L* - {ε} (Kleene Plus excludes ε)
  8. ✓ L ⊆ L* (original is subset)
  9. ✓ Regular languages closed under Kleene Star
  10. ✓ In regex, * means “zero or more”

Common Mistakes to Avoid

❌ Mistake 1: ∅* = ∅
✓ Correct: ∅* = {ε}

❌ Mistake 2: L* doesn’t include ε
✓ Correct: L* always includes ε (from L⁰)

❌ Mistake 3: {a}_ = {a, aa, aaa, …} (missing ε)
✓ Correct: {a}_ = {ε, a, aa, aaa, …}

❌ Mistake 4: L* is finite
✓ Correct: L* is infinite (unless L = ∅ or {ε})

❌ Mistake 5: (L*)* ≠ L*
✓ Correct: (L*)_ = L_ (idempotent)

❌ Mistake 6: L* = L
✓ Correct: L ⊆ L*, but L* also includes ε and repetitions

Practice Questions

Q1: What is {0}*?

Answer: {0}* = {ε, 0, 00, 000, 0000, …} = {0ⁿ | n ≥ 0}

Q2: What is ∅*?

Answer: ∅* = {ε}

Q3: If L = {ab, ba}, list first few strings in L*.

Answer: L* = {ε, ab, ba, abab, abba, baab, baba, ababab, …}

Q4: Is ε ∈ {a, b}*?

Answer: Yes, ε is always in L* (from L⁰)

Q5: What is ({ε})*?

Answer: {ε}* = {ε}

Q6: Express L⁺ in terms of L*.

Answer: L⁺ = L · L* = L* - {ε}

Q7: Is {a}* = {a}⁺ ∪ {ε}?

Answer: Yes! This is the relationship between star and plus.

Q8: What is (L*)* equal to?

Answer: (L*)* = L* (idempotent property)

Summary

  • Kleene Star (L*) generates all possible concatenations of strings from L
  • Includes ε (from L⁰ = {ε})
  • L* is infinite for any non-empty, non-{ε} language
  • ∅* = {ε} (special case - don’t forget!)
  • Idempotent: (L*)* = L*
  • L⁺ is similar but excludes ε
  • Regular languages closed under Kleene Star
  • Fundamental operation in regular expressions (*)
  • Used for “zero or more repetitions” patterns

Kleene Star is one of the most powerful operations, allowing us to express infinite languages concisely and enabling pattern matching in real-world applications!