TOPICS
Search

Kleene Star


The Kleene star of a formal language L is L^*= union _(n>=0)L^n, where L^n consists of concatenations of n words from L and L^0 contains only the empty word of length 0. Thus L^* includes the empty word, irrespective of whether L does. It contains finite concatenations rather than infinite words.

Kleene star is an operation in regular expressions. For a regular language, the minimum possible maximum nesting depth of Kleene stars among regular expressions denoting the language defines its star height; when complement is also allowed, the corresponding minimum depth is generalized star height (Kirsten 2005, p. 492).


See also

Concatenation, Formal Language, Generalized Star Height, Regular Expression, Star Height, Word

Explore with Wolfram|Alpha

References

Kirsten, D. "Distance Desert Automata and the Star Height Problem." RAIRO Inform. Théor. Appl. 39, 455-509, 2005. https://doi.org/10.1051/ita:2005027.

Cite this as:

Weisstein, Eric W. "Kleene Star." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KleeneStar.html

Subject classifications