Kleene Star

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''.

DEFINITION AND NOTATION

Given
:

V_0=\{\epsilon\}\,

define recursively the set
:

V_{i+1}=\{wv : w\in V_i \mbox{ and }  v \in V\}\,

where

i > 0\,.

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

=\bigcup_{i=0}^{\infty} V_i = \left \{\epsilon 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

.

EXAMPLES

Example of Kleene star applied to set of strings:

= {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Example of Kleene star applied to set of characters:

GENERALIZATION

The Kleene star is often generalized for any Monoid (''M'',

\circ

), that is, a set ''M'' and binary operation

\circ

on ''M'' such that

( Associativity ) $orall a,b,c \in M:~ (a \circ b) \circ c = a \circ (b \circ c)$

	CATEGORIES ABOUT KLEENE STAR

	formal languages

Information About