Kleenestjerne

I matematisk logikk og informatikk er kleenestjerna (også kalt kleenetillukning og kleeneoperatoren) en unær operator på ei mengde symboler eller strenger. Operasjonen er ofte skrevet som V* hvor V er mengda det er snakk om. Det er ofte brukt i regulæruttrykk og var også der operatoren først ble introdusert i den betydning «null eller mer».

Hvis V er ei mengde bestående av symboler vil kleenestjerna av V være mengda over alle strenger over alfabetet bestående av symbolet inkludert den tomme strengen. Dette kalles også språket over alfabetet bestående av de gitte symbolene.

Hvis V er ei mengde bestående av strenger vil V være den minste mengda av V som inneholder den tomme strengen og som er lukket under operasjonen konkatenering.

Kleenestjerna over mengda V kan også beskrives som mengda over alle strenger som blir generert av å konkatenere vilkårlige elementer i V.

 Formell definisjon 
Gitt ei mengde V la V være følgende mengde. I dette tilfellet språket bestående av bare den tomme strengen.
 V0 = {ε},
 V1 = V
Definer så følgende mengde rekursivt og man vil få tillukningen av denne mengda.
 Vi+1 = { wv : w ∈ Vi and v ∈ V } for enhver i>0.

 Eksempler 
 Kleenestjerna av ei mengde bestående av symbolene a, b og c vil være følgende uendelige mengde.

{«a», «b», «c»}* = { ε, «a», «b», «c», «aa», «ab», «ac», «ba», «bb», «bc», «ca», «cb», «cc», «aaa», «aab», …}.

Kleenestjerna av ei mengde må ikke være uendelig. Kleenestjerna av den tomme mengden er følgende mengde

 ∅* = {ε}

 Litteratur 


Kategori:Formelle språk