Kleene star

Kleene star

In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set "V" is written as "V"*. It is widely used for regular expressions, which is the context in which it was introduced by Stephen Kleene to characterise certain automata.

# If "V" is a set of strings then "V"* is defined as the smallest superset of "V" that contains λ (the empty string) and is closed under the string concatenation operation. This set can also be described as the set of strings that can be made by concatenating zero or more strings from "V".
# If "V" is a set of symbols or characters then "V"* is the set of all strings over symbols in "V", including the empty string.

Definition and notation

Given: V_0={lambda}, define recursively the set: V_{i+1}={wv : win V_i mbox{ and } v in V}, where i ge 0,.

If V is a formal language, then the i-th power of the set V is shorthand for the concatenation of set V with itself i times. That is, V_i can be understood to be the set of all strings of length i, formed from the symbols in V.

The definition of Kleene star on V is V^*=igcup_{i in N} V_i = left {lambda ight} cup V_1 cup V_2 cup V_3 cup ldots

That is, it is the collection of all possible finite-length strings generated from the symbols in V.

In some formal language studies, (e.g. AFL Theory) a variation on the Kleene star operation called the "Kleene plus" is used. The Kleene plus omits the V_0 term in the above union. In other words, the Kleene plus on V is V^+=igcup_{i in N^{star V_i = V_1 cup V_2 cup V_3 cup ldots

Examples

Example of Kleene star applied to 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 set of characters:: {'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", ...}

Example of Kleene star applied to the empty set::varnothing ^* ={lambda}

Example of Kleene plus applied to the empty set::varnothing ^+ = varnothing varnothing ^* ={}= varnothing

Generalization

Strings form a monoid with concatenation as the binary operation and λ the identity element. The Kleene star is defined for any monoid, not just strings.

See also

* Kleene algebra
* Extended Backus-Naur form
* Pumping lemma
* Star height problem, generalized star height problem, star-free language
* Regular expressions


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Kleene Star — Die Kleenesche Hülle (auch endlicher Abschluss, Kleene * Abschluss oder Verkettungshülle genannt) eines Alphabets Σ oder einer formalen Sprache L ist die Menge aller Wörter, die durch beliebige Konkatenation (Verknüpfung) von Symbolen des… …   Deutsch Wikipedia

  • Kleene star — noun The asterisk, ,, used as an operator to concatenate zero or more strings from a given set, widely used in regular expressions. Syn: Kleene closure …   Wiktionary

  • Kleene algebra — In mathematics, a Kleene algebra (named after Stephen Cole Kleene, IPAEng|ˈkleɪni as in clay knee ) is either of two different things:* A bounded distributive lattice with an involution satisfying De Morgan s laws, and the inequality x ∧− x ≤ y… …   Wikipedia

  • Star (disambiguation) — A star is a luminous cosmic body. For uses of stars as a symbol, see List of symbolic stars.Star or stars may also refer to:Places*Star Mountains, a mountain range in Papua New GuineaUnited Kingdom*Star, Anglesey, Wales *Star, Fife, Scotland… …   Wikipedia

  • Star height problem — The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i. e. with a limited nesting depth of Kleene stars. Specifically, is a nesting… …   Wikipedia

  • Star-free language — A regular language is said to be star free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, boolean operators and concatenation but no Kleene star. For instance, the language of… …   Wikipedia

  • Stephen Cole Kleene — Infobox Scientist name = Stephen Kleene caption = birth date = birth date|1909|1|5 birth place = USA death date = death date and age|1994|1|25|1909|1|5 death place = residence = USA nationality = USA field = Mathematics work institutions =… …   Wikipedia

  • Generalized star height problem — The generalized star height problem in formal language theory is the open question whether all regular languages can be expressed using regular expressions with a built in complement operator of limited star height, i. e. with a limited nesting… …   Wikipedia

  • Fermeture De Kleene — Pour les articles homonymes, voir Fermeture. La fermeture de Kleene, parfois appelée étoile de Kleene ou encore fermeture itérative, est un opérateur unaire utilisé pour décrire les langages formels. Appliquée à un ensemble V, elle a pour… …   Wikipédia en Français

  • Fermeture de kleene — Pour les articles homonymes, voir Fermeture. La fermeture de Kleene, parfois appelée étoile de Kleene ou encore fermeture itérative, est un opérateur unaire utilisé pour décrire les langages formels. Appliquée à un ensemble V, elle a pour… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”