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

Kleene Star and Plus on Languages

Define Kleene star (L*) and Kleene plus (L+) operations on languages, generating iterations and closures.

Kleene Star and Plus on Languages

What you'll learn: How to use Kleene star and Kleene plus to generate infinite sets of strings from a language.

You've already seen the Kleene star applied to individual strings (like a* meaning "a repeated zero or more times"). Now we extend this powerful operation to entire languages—sets of strings.

Kleene Star on Languages (L*)

Given a language L, the Kleene star L* produces a new language containing:

  • The empty string ε (zero concatenations)
  • All strings in L (one concatenation)
  • All strings formed by concatenating any two strings from L (two concatenations)
  • All strings formed by concatenating any three strings from L (three concatenations)
  • ...and so on, infinitely

Formally: L* = {ε} ∪ L ∪ LL ∪ LLL ∪ ...

Example: If L = {ab, c}, then L* includes:

  • ε (empty)
  • ab, c (from L)
  • abab, abc, cab, cc (concatenating two strings)
  • ababab, ababc, abcab, abcc, cabab, cabc, ccab, ccc (three strings)
  • ...and infinitely more

Kleene Plus on Languages (L⁺)

The Kleene plus L⁺ is similar but excludes the empty string—it requires at least one concatenation:

Formally: L⁺ = L ∪ LL ∪ LLL ∪ ... = LL*

Using the same example L = {ab, c}, L⁺ contains everything in L* except ε.

Analogy

Think of L* as "make zero or more purchases from menu L" and L⁺ as "make at least one purchase from menu L." You can order the same item multiple times or mix items freely.

Key Takeaway: Kleene star (L*) generates all possible concatenations of strings from L including the empty string, while Kleene plus (L⁺) requires at least one string from L, creating infinite languages from finite ones.