Kleene-ster

In de wiskunde en informatica is de Kleene-ster een unaire operator op een verzameling strings of een verzameling symbolen. Het toepassen van de Kleene-ster op de verzameling ${\displaystyle V}$ wordt genoteerd als ${\displaystyle V^{*}}$. De operator wordt veel gebruikt in reguliere expressies waarin hij geïntroduceerd werd door Stephen Kleene om eindige automaten te karakteriseren.

1. Als ${\displaystyle V}$ een verzameling strings is, wordt de Kleene-ster gedefinieerd als de kleinste superset van ${\displaystyle V}$ die ${\displaystyle \epsilon }$ (de lege string) bevat en die gesloten is onder concatenatie van strings.
2. Als ${\displaystyle V}$ een verzameling symbolen is, is ${\displaystyle V^{*}}$ de verzameling met alle strings van symbolen uit ${\displaystyle V}$, inclusief de lege string.

Definitie

We definiëren

${\displaystyle V_{0}=\{\epsilon \}}$

en op recursieve wijze de verzameling:

${\displaystyle V_{i+1}=\{wv\mid w\in V_{i}{\mbox{ en }}v\in V\}}$, met ${\displaystyle i\geq 0}$.

Als ${\displaystyle V}$ een formele taal is, dan bevat ${\displaystyle V_{i}}$ alle mogelijke strings die ontstaan door ${\displaystyle i}$ keer een element uit ${\displaystyle V}$ te nemen (mogelijk dezelfde) en deze te concateneren.

De Kleene-ster kan nu gedefinieerd worden als:

${\displaystyle V^{*}=\bigcup _{i=0}^{\infty }V_{i}=\left\{\epsilon \right\}\cup V_{1}\cup V_{2}\cup V_{3}\cup \ldots }$

${\displaystyle V^{*}}$ bevat dus alle mogelijke strings met eindige lengte die gegenereerd kunnen worden met symbolen uit ${\displaystyle V}$.

Voorbeelden

De Kleene-ster van een verzameling met strings:

${\displaystyle \{ab,c\}^{*}=\{\epsilon ,ab,c,abab,abc,cab,cc,ababab,ababc,abcab,abcc,cabab,cabc,ccab,ccc,\ldots \}}$

De Kleene-ster van een verzameling met symbolen:

${\displaystyle \{a,b,c\}^{*}=\{\epsilon ,a,b,c,aa,ab,ac,ba,bb,bc,\ldots \}}$

Generalisatie

De Kleene-ster wordt vaak gegeneraliseerd voor een willekeurige monoïde ${\displaystyle (M,{\circ })}$, een verzameling ${\displaystyle M}$ en een binaire operatie ${\displaystyle \circ }$ op ${\displaystyle M}$, zodanig dat:

• (geslotenheid) ${\displaystyle \forall a,b\in M:~a\circ b\in M}$
• (associativiteit) ${\displaystyle \forall a,b,c\in M:~(a\circ b)\circ c=a\circ (b\circ c)}$