Kleenestjerne

I matematisk logikk og informatikk er kleenestjerna (òg kalla kleenetillukninga og kleeneoperatoren) ein unær operator på ei mengd symbol eller strengar. Operasjonen er ofte skriven som V* der V er mengda det er snakk om. Det er ofte brukt i regulæruttrykk og var òg der operatoren først vart introdusert i tydinga «null eller meir». Kleenestjerna er kalla opp etter den amerikanske matematikaren Stephen Kleene.

Viss V er ei mengd av symbol vil kleenestjerna av V vera mengda over alle strengar over alfabetet av symbolet inkludert den tomme strengen. Dette vert òg kalla språket over alfabetet av dei gjevne symbola.

Viss V er ei mengd av strengar vil V vera den minste mengda av V som inneheld den tomme strengen og som er lukka under operasjonen konkatenering.

Kleenestjerna over mengda V kan òg skildrast som mengda over alle strengar som vert genererte av å konkatenera vilkårlege element i V.

Formell definisjon

Gjeve ei mengd V, la V vera følgjande mengd. I dette høvet språket av berre den tomme strengen.

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

$V_{1}=V$

Definer så følgjande mengd rekursivt og ein vil få tillukninga av denne mengda.

$V_{i+1}=\{wv:w\in V_{i}\quad og\quad v\in V\}$

for kvar og ein $i>0$

Døme

Kleenestjerna av ei mengd av symbola a, b og c vil vera følgjande uendelege mengd.

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

Kleenestjerna av ei mengd må ikkje vera uendeleg. Kleenestjerna av den tomme mengda er følgjande mengd

∅* = {ε}

Litteratur

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