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.

V₀ = {ε},

V₁ = V

Definer så følgende mengde rekursivt og man vil få tillukningen av denne mengda.

V_i+1 = { wv : w ∈ V_i 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

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st utg.). Addison-Wesley.