Editing Kleene star

{{Short description|Unary operation on string sets}}
{{Use dmy dates|date=September 2022}}
In [[mathematical logic]] and [[theoretical computer science]], the '''Kleene star''' (or '''Kleene operator''' or '''Kleene closure''') is a [[unary operation]] on a [[Set (mathematics)|set]] {{mvar|V}} to generate a set {{mvar|V*}} of all finite-length strings<ref group="note" name="strings"/> that are composed of zero or more repetitions of members from {{mvar|V}}. It was named after American mathematician [[Stephen Cole Kleene]], who first introduced and widely used it to characterize [[Automata theory|automata]] for [[regular expression]]s. In mathematics, it is more commonly known as the [[free monoid]] construction.

== Definition ==
Given a set <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>
<math>V^i</math> is called the <math>i</math>-th power of <math>V</math>, it is a shorthand for the [[Concatenation#Concatenation of sets of strings|concatenation]] of <math>V</math> by itself <math>i</math> times. That is, ''<math>V^i</math>'' can be understood to be the set of all strings that can be represented as the concatenation of <math>i</math> members from <math>V</math>.

The definition of Kleene star on <math>V</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''<sup>*</sup> of ''L'' is defined to be <math display="inline">\bigcup_{i=0}^\infty L^i</math>.}}</ref>

:<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>

== 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> term in the above union. 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"}<sup>*</sup> = { ε, "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"}<sup>*</sup> = { ε, "a", "ab", "b", "aa", "aab", "aba", "abab", "abb", "ba", "bab", "bb", ...};<BR>e.g. the string "aab" can be obtained in several different ways. The [[Sardinas-Patterson algorithm]] can be used to check for a given ''V'' whether any member of ''V''<sup>*</sup> can be obtained in more than one way.

Example of Kleene and Kleene plus applied to a set of characters:
: {"a", "b", "c"}<sup>*</sup> = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.
: {"a", "b", "c"}<sup>+</sup> = { "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]], then ''<math>V^*</math>'' is a countably infinite set.<ref>{{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>(V^{*})^{*}=V^{*}</math>, which means that the Kleene star operator is an [[idempotent]] [[unary operator]], as <math>(V^{*})^{i}=V^{*}</math> for every <math>i\geq 1</math>.
* <math>V^{*}=\{\varepsilon\}</math>, if <math>V</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''<sup>*</sup> is the smallest submonoid of ''M'' containing ''S''; that is, ''S''<sup>*</sup> contains the neutral element of ''M'', the set ''S'', and is such that if ''x'',''y'' ∈ ''S''<sup>*</sup>, then ''x''⋅''y'' ∈ ''S''<sup>*</sup>.

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''<sup>+</sup> 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]]