Kleene star

2025-09-16T21:02:45Z

2804:248:F40B:4900:E5ED:5680:C4B0:E085: Fix spelling of "Kleene star of a language" explanation

{{Short description|Unary operation on string sets}}
{{Use dmy dates|date=September 2022}}
In [[formal language theory]], the '''Kleene star''' (or '''Kleene operator''' or '''Kleene closure''') refer to two related [[unary operation]]s, that can be applied either to an [[Alphabet (formal languages)|alphabet]] of [[Symbol (formal)|symbols]] or to a [[formal language]], a set of strings (finite sequences of symbols).

The Kleene star operator on an alphabet {{mvar|V}} generates the set {{mvar|V*}} of all finite-length strings over {{mvar|V}},<ref group="note" name="strings"/> that is, finite sequences whose elements belong to {{mvar|V}}; in mathematics, it is more commonly known as the [[free monoid]] construction. The Kleene star operator on a language {{mvar|L}} generates another language {{mvar|L*}}, the set of all strings that can be obtained as a [[concatenation]] of zero or more members of {{mvar|L}}. In both cases, repetitions are allowed.

The Kleene star operators are named after American mathematician [[Stephen Cole Kleene]], who first introduced and widely used it to characterize [[Automata theory|automata]] for [[regular expression]]s.

== Of an alphabet ==
Given an alphabet <math>V</math>,
define
:<math>V^{0}=\{\varepsilon\}</math> (the set consists only of the empty string),
:<math>V^{1}=V,</math>
and define recursively the set
:<math>V^{i+1}=\{wv: w\in V^{i} \text{ and } v\in V \}</math> for each <math>i>0,</math>
where <math>wv</math> denotes the string obtained by appending the single character <math>v</math> to the end of <math>w</math>. Here, ''<math>V^i</math>'' can be understood to be the set of all strings of length exactly <math>i</math>, with characters from <math>V</math>.

The definition of Kleene star on <math>V</math> is<ref name=nayuki/>
:<math> V^*=\bigcup_{i \ge 0 }V^i = V^0 \cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots.</math>

==Of a language==
Given a language <math>L</math> (any finite or infinite set of strings), define
:<math>L^{0}=\{\varepsilon\}</math> (the language consisting only of the empty string),
:<math>L^{1}=L,</math>
and define recursively the set
:<math>L^{i+1}=\{wv: w\in L^{i} \text{ and } v\in L \}</math> for each <math>i>0,</math>
where <math>wv</math> denotes the string obtained by concatenating <math>w</math> and <math>v</math>. Here, ''<math>L^i</math>'' can be understood to be the set of all strings that can be obtained by concatenating exactly <math>i</math> strings from <math>L</math>, allowing repetitions.

The definition of Kleene star on <math>L</math> is<ref>{{cite book |last1=Fletcher |first1=Peter |last2=Hoyle |first2=Hughes |last3=Patty |first3=C. Wayne |date=1991 |title=Foundations of Discrete Mathematics |publisher=Brooks/Cole |isbn=0534923739 |page=656 |quote=The '''Kleene closure''' ''L''* of ''L'' is defined to be <math display="inline">\bigcup_{i=0}^\infty L^i</math>.}}</ref>
:<math> L^*=\bigcup_{i \ge 0 }L^i = L^0 \cup L^1 \cup L^2 \cup L^3 \cup L^4 \cup \cdots.</math>

== Kleene plus ==
In some [[formal language]] studies, (e.g. [[Abstract family of languages|AFL theory]]) a variation on the Kleene star operation called the ''Kleene plus'' is used. The Kleene plus omits the <math>V^{0}</math> or <math>L^0</math> term in the above unions. In other words, the Kleene plus on <math>V</math> is

:<math>V^+=\bigcup_{i \geq 1} V^i = V^1 \cup V^2 \cup V^3 \cup \cdots,</math>

or

:<math>V^+ = V^*V.</math><ref group="note" name="kleene-plus"/>

== Examples ==
Example of Kleene star applied to a set of strings:
: {"ab","c"}* = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.
Example of Kleene star applied to a set of strings without the [[prefix property]]:
: {"a","ab","b"}* = { ε, "a", "ab", "b", "aa", "aab", "aba", "abab", "abb", "ba", "bab", "bb", ...}; In this example, the string "aab" can be obtained in two different ways. The [[Sardinas-Patterson algorithm]] can be used to check for a given ''V'' whether any member of ''V''* can be obtained in more than one way.

Example of Kleene and Kleene plus applied to a set of characters (following the [[C programming language]] convention where a character is denoted by single quotes and a string is denoted by double quotes):
: {'a', 'b', 'c'}* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.
: {'a', 'b', 'c'}+ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

== Properties ==

* If <math>V</math> is any [[finite set|finite]] or [[countably infinite set]] of characters, then ''<math>V^*</math>'' is a countably infinite set.<ref name=nayuki>{{cite web |author=Nayuki Minase |date=10 May 2011 |title=Countable sets and Kleene star |work=Project Nayuki |url=http://www.nayuki.io/page/countable-sets-and-kleene-star |access-date=11 January 2012}}</ref> As a result, each [[formal language]] over a finite or countably infinite alphabet <math>\Sigma</math> is countable, since it is a subset of the countably infinite set <math>\Sigma^{*}</math>.
* <math>(L^{*})^{*}=L^{*}</math>, which means that the Kleene star operator is an [[idempotent]] [[unary operator]], as <math>(L^{*})^{i}=L^{*}</math> for every <math>i\geq 1</math>.
* <math>V^{*}=\{\varepsilon\}</math>, if <math>V</math> is the [[empty set]] ∅. For the version of the Kleene star operator on languages, <math>L^{*}=\{\varepsilon\}</math> when <math>L</math> is either the [[empty set]] ∅ or the singleton set <math>\{\varepsilon\}</math>.

== Generalization ==

[[String (computer science)|Strings]] form a [[monoid]] with concatenation as the binary operation and ε the identity element. In addition to strings, the Kleene star is defined for any monoid.
More precisely, let (''M'', ⋅) be a monoid, and ''S'' ⊆ ''M''. Then ''S''* is the smallest submonoid of ''M'' containing ''S''; that is, ''S''* contains the neutral element of ''M'', the set ''S'', and is such that if ''x'',''y'' ∈ ''S''*, then ''x''⋅''y'' ∈ ''S''*.

Furthermore, the Kleene star is generalized by including the *-operation (and the union) in the [[algebraic structure]] itself by the notion of [[complete star semiring]].<ref name="droste">{{cite book |last1=Droste |first1=M. |last2=Kuich |first2=W. |date=2009 |title=Handbook of Weighted Automata |url=https://archive.org/details/handbookweighted00dros |url-access=limited |chapter=Chapter 1: Semirings and Formal Power Series |series=Monographs in Theoretical Computer Science |publisher=Springer |doi=10.1007/978-3-642-01492-5_1 |isbn=978-3-642-01491-8 |page=[https://archive.org/details/handbookweighted00dros/page/n23 9]}}</ref>

==See also==
* [[Wildcard character]]
* [[Glob (programming)]]

==Notes==
{{reflist|group=note|refs=
<ref name="strings">It is called "strings" for historical reasons, since Kleene invented it in the context of automata theory, but the idea has been generalized such that each symbol in a string is not necessarily a single [[character (computing)|character]] {{Crossreference|selfref=no|(see {{Section link|#Generalization}})}}.</ref>
<ref name="kleene-plus">This equation holds because every member of ''V''+ can be generated by first picking a member from ''V*'', and then picking a member from ''V'' for appending. This two-step process does not generate ε since the second step never pick an ε.</ref>
}}

==References==
{{Reflist}}

==Further reading==
*{{cite book |last1=Hopcroft |first1=John E. |author-link1=John Hopcroft |last2=Ullman |first2=Jeffrey D. |author-link2=Jeffrey Ullman |date=1979 |title=Introduction to Automata Theory, Languages, and Computation |title-link=Introduction to Automata Theory, Languages, and Computation |edition=1st |publisher=[[Addison-Wesley]]}}

[[Category:Formal languages]]
[[Category:Grammar]]
[[Category:Natural language processing]]

Vero - Wikipedia - User contributions [en]

Kleene star