Does L* always contain ε?

Yes. The zero-concatenation case guarantees it.

No. For example, ∅* and {ε}* both equal {ε}. A language containing a nonempty string has arbitrarily long repetitions of that string under star.

Does applying star twice change the language?

No. (L*)* = L*: concatenating finite sequences of already permitted finite concatenations still produces a finite concatenation from L.

AI Glossary / Natural language and speech / Intermediate

Kleene star

Definition

The Kleene star is an operation on a language or pattern that allows zero or more finite repetitions. For a language L, its star L* contains every string formed by concatenating any finite number of strings from L, including none. Therefore L* always contains the empty string, written ε.

What it means

A formal language is a set of strings. Applying the star builds a new set by allowing repeated selection and concatenation of strings from the original set.
Zero repetitions matters: choosing no strings produces ε, a string with length zero. That is different from an empty set, which contains no strings at all.
In regular expressions, a star applies to the preceding expression. Grouping changes its scope. Thus (ab)* repeats the two-character block ab, while ab* means one a followed by zero or more b characters. The notation is precise even though practical programming libraries can add their own matching options.

How it works

Define L⁰ = {ε}. Define L¹ = L, and let L² contain all concatenations of two members of L. Continue similarly for each finite repetition count.
The star is the union L* = L⁰ ∪ L¹ ∪ L² ∪ ... . Each individual result uses a finite number of pieces, even when the whole set contains infinitely many different strings.
The pieces need not all be identical if L has several members. For example, {a, b}* includes mixed strings such as abba, not only runs of a or runs of b.
If the input is an alphabet Σ viewed as one-character strings, Σ* is the set of all finite strings over that alphabet.

Three practical examples

A text-pattern rule permits any number of optional separator characters, including none, by applying a star to the separator pattern.
A formal-language exercise describes all binary strings as {0, 1}*, explicitly including the empty string.
A parser developer distinguishes a repeated whole block from repetition of only its last character by adding the appropriate grouping.

Think of it this way

Think of making a necklace by choosing zero or more pieces from an allowed box and joining them in order. Choosing no pieces corresponds to the empty string. The analogy is bounded because formal concatenation does not add spaces, knots, or separators unless those symbols are already part of the chosen pieces.

Worked example

Let L = {ab, c}. Zero selections produce ε. One selection produces ab or c. Two selections produce abab, abc, cab, or cc.
Three selections include ababc, obtained by choosing ab, then ab, then c. The string abcab is also included because it is ab followed by c followed by ab.
The string ac is not included: the available a appears only as part of the complete block ab, and concatenation cannot remove that b. Likewise, ba is not obtainable from these pieces.
Notice that the strings of L* have different character lengths because the permitted pieces have lengths two and one. Repetition count therefore need not equal character count.
Now compare the patterns (ab)* and ab*. The first includes ε, ab, and abab, but excludes abb. The second includes a, ab, and abb, but excludes ε and abab when interpreted as a full-string pattern. These checks demonstrate both the zero-repeat case and the importance of scope.

Illustrative case study

In a fictional project, Cedar Forms writes a validator for identifiers that may have a numeric suffix. A developer uses a repeated-digit pattern and accidentally permits an empty suffix in a field whose specification requires at least one digit.
Reviewers add the empty input to the test cases and distinguish the optional-suffix field from the mandatory-number field. They also check whether the application matches the entire field or merely finds a matching substring.
The imagined case shows how a small formal distinction affects validation. It does not claim that one regular expression verifies every semantic condition on an identifier.

Common misconceptions and mistakes

Star means zero or more repetitions, not one or more. The latter is commonly expressed with a plus operator or by concatenating L with L*.
Star does not itself mean “any character.” In a regular expression, the repeated operand determines what can occur.
The empty string ε and empty language ∅ are different. In particular, ∅* = {ε}, because zero repetitions remain possible even though no nonempty selection can be made.
An infinite language can contain only finite strings. Ordinary Kleene star does not introduce infinite-length strings.
Greedy or lazy matching behavior in a programming library is separate from the formal set of strings described by repetition.

Business use

This concept matters in text validation, tokenization, search patterns, and grammar specifications. A misunderstanding of zero repetitions can allow missing values, while incorrect grouping can accept or reject the wrong sequences.
For a business form or import rule, write concrete accepted and rejected examples, including empty and single-character cases. Check the application's full-match versus substring-search behavior and the exact character set. A theoretically correct repetition pattern can still be used incorrectly by the surrounding software.

Check your understanding

If L = {xy}, is xxyy in L*? Is ε in L*?

Answer: xxyy is not, because repeating the complete block xy gives xy, xyxy, and so on. ε is included through zero repetitions.

Related terms

Regular expression
Formal language
Pattern matching
concatenation
alphabet
empty string
Kleene plus
finite automaton
closure operation

Learn next

list the first few repetition levels of a small language, then compare star with plus and optional occurrence. When testing a programming implementation, verify grouping and full-string matching separately from the underlying language definition.

Sources

Cornell CS 2800, original “Regular expressions” lecture: https://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec26-re.html. Stanford CS103, original “Guide to Regular Expressions”: https://web.stanford.edu/class/archive/cs/cs103/cs103.1264/guide_to_regexes. These introduce repetition and composition; the block examples above are original teaching material. Independent source review: The Cornell repetition definition and Stanford composition guide were read. The entry retains finite powers explicitly rather than reproducing Cornell’s imprecise displayed formula.

Previous: Kleene + Next: KLT (Kanade - Lucas - Tomasi) tracker