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.