## FANDOM

174 Pages

The Kleene star is a unary operation on alphabets or sets of strings that creates the set of all finite concatenations of those strings.

## Formal definitionEdit

Given any set $A$ define

$A_0=\{ \epsilon \}$ (where $\epsilon$ is the empty string)
$A_1=A$
$A_{i+1}=\{xy|w \in A_i \land y \in A \}$

where $xy$ is the concatenation of strings $x$ and $y$.

Then Kleene star on $A$ is defined as:

$A^*=\bigcup_{i \in \mathbb{N}}V_i=V_1 \cup V_2 \ldots$.

## Kleene plusEdit

Kleene star without the empty string is kleene plus. Formally: $V^+=V^* \setminus {\epsilon}$