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

Powers of Strings and Kleene Star

Define string exponentiation (x^n) and the Kleene star operation (Σ*) generating all possible strings.

Powers of Strings and Kleene Star

You'll learn how to generate all possible combinations of strings using exponentiation and the powerful Kleene star operation.

String Exponentiation

Just as we can multiply a number by itself (3² = 3 × 3), we can concatenate a string with itself multiple times. String exponentiation uses the notation x^n to represent string x concatenated with itself n times.

For example:

  • x⁰ = ε (the empty string — anything to the zero power gives the "identity")
  • x¹ = x
  • x² = xx (x concatenated with x)
  • x³ = xxx

If x = "ab", then:

  • x⁰ = ε
  • x¹ = "ab"
  • x² = "abab"
  • x³ = "ababab"

The Kleene Star (Σ*)

The Kleene star operation, written as Σ*, generates every possible string you can make from an alphabet Σ, including the empty string. It's like having infinite exponentiation powers at once.

Think of Σ* as an infinite set containing:

  • The empty string (ε)
  • Every single character from Σ
  • Every possible two-character combination
  • Every possible three-character combination
  • ...and so on forever

For alphabet Σ = {a, b}:

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

This set is countably infinite — it never ends, but we can list its members systematically (by length, then alphabetically).

Key Takeaway: String exponentiation x^n repeats a string n times through concatenation, while the Kleene star Σ* generates the infinite set of all possible strings (including ε) that can be formed from an alphabet.