Kleene star
In formal language theory, the Kleene star (or Kleene operator or Kleene closure) refers to two related unary operations, that can be applied either to an alphabet of symbols or to a formal language, a set of strings (finite sequences of…
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In formal language theory, the Kleene star (or Kleene operator or Kleene closure) refers to two related unary operations, that can be applied either to an alphabet of symbols or to a formal language, a set of strings (finite sequences of symbols). The Kleene star operator on an alphabet generates the set of all finite-length strings over , that is, finite sequences whose elements belong to ; in mathematics, it is more commonly known as the free monoid construction.
The Kleene star operator on a language generates another language , the set of all strings that can be obtained as a concatenation of zero or more members of . 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 for regular expressions.
V^{0}=\{\varepsilon\} (the set consists only of the empty string), V^{1}=V, and define recursively the set V^{i+1}=\{wv: w\in V^{i} \text{ and } v\in V \} for each i>0, where wv denotes the string obtained by appending the single character v to the end of w . Here, V^i can be understood to be the set of all strings of length exactly i , with characters from V . The definition of Kleene star on V is V^*=\bigcup_{i \ge 0 }V^i = V^0 \cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots.
Of a language
Given a language L (any finite or infinite set of strings), define L^{0}=\{\varepsilon\} (the language consisting only of the empty string), L^{1}=L, and define recursively the set L^{i+1}=\{wv: w\in L^{i} \text{ and } v\in L \} for each i>0, where wv denotes the string obtained by concatenating w and v . Here, L^i can be understood to be the set of all strings that can be obtained by concatenating exactly i strings from L , allowing repetitions. The definition of Kleene star on L is L^*=\bigcup_{i \ge 0 }L^i = L^0 \cup L^1 \cup L^2 \cup L^3 \cup L^4 \cup \cdots.
V^+=\bigcup_{i \geq 1} V^i = V^1 \cup V^2 \cup V^3 \cup \cdots, or V^+ = V^*V. {"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", ...}.
(L^{*})^{*}=L^{*} , which means that the Kleene star operator is an idempotent unary operator, as (L^{*})^{i}=L^{*} for every i\geq 1 . V^{*}=\{\varepsilon\} , if V is the empty set ∅. For the version of the Kleene star operator on languages, L^{*}=\{\varepsilon\} when L is either the empty set ∅ or the singleton set \{\varepsilon\} .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1376656846 under CC BY-SA 4.0; modifications have been made.