Kleenestjerne

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

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[rediger | rediger kilde]

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 : wVi and vV } for enhver i>0.

Eksempler[rediger | rediger kilde]

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[rediger | rediger kilde]