Kleene star
E601578
The Kleene star is a fundamental operation in formal language theory and regular expressions that denotes the set of all finite concatenations (including the empty string) of a given symbol or pattern.
Statements (43)
| Predicate | Object |
|---|---|
| instanceOf |
closure operator
ⓘ
operation in formal language theory ⓘ unary operator on sets of strings ⓘ |
| alsoKnownAs | Kleene closure NERFINISHED ⓘ |
| appearsIn |
Kleene’s theorem on regular sets
NERFINISHED
ⓘ
definition of regular expressions ⓘ |
| closureProperty |
preserves context-freeness of languages
ⓘ
preserves regularity of languages ⓘ |
| codomain | sets of strings over the same alphabet ⓘ |
| differenceFrom | Kleene plus excludes the empty string ⓘ |
| domain | sets of strings over an alphabet ⓘ |
| example |
If L = {ab} then L* = {ε, ab, abab, ababab, …}
ⓘ
If L = {a} then L* = {ε, a, aa, aaa, …} ⓘ |
| field |
automata theory
ⓘ
formal language theory ⓘ mathematical logic ⓘ theoretical computer science ⓘ |
| formalDefinition | For a language L over an alphabet Σ, L* = ⋃_{n≥0} L^n ⓘ |
| includesEmptyString | true ⓘ |
| mathematicalStructure | idempotent with respect to application: (L*)* = L* ⓘ |
| namedAfter | Stephen Cole Kleene NERFINISHED ⓘ |
| notationInRegex | R* denotes zero or more repetitions of pattern R ⓘ |
| property |
(L*)* = L*
ⓘ
L* = {ε} ∪ L*·L ⓘ L* = {ε} ∪ L·L* ⓘ L* always contains the empty string ε ⓘ L* is infinite if L contains a non-empty string ⓘ L* is the smallest superset of L that is closed under concatenation and contains ε ⓘ if L is a regular language then L* is regular ⓘ if L is context-free then L* is context-free ⓘ {ε}* = {ε} ⓘ ∅* = {ε} ⓘ |
| relatedConcept | Kleene plus NERFINISHED ⓘ |
| symbol | * ⓘ |
| usedIn |
Kleene algebra
NERFINISHED
ⓘ
compiler construction ⓘ finite automata ⓘ lexical analysis ⓘ pattern matching ⓘ program verification ⓘ regular expressions ⓘ regular languages ⓘ text processing ⓘ |
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.