Kleene-ster

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

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

Definitie[bewerken]

We definiëren

 V_0=\{\epsilon\}\,

en op recursieve wijze de verzameling:

 V_{i+1}=\{wv : w\in V_i \mbox{ en }  v \in V\}\, met i > 0\,.

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

De Kleene-ster kan nu gedefinieerd worden als:

 V^*=\bigcup_{i=0}^{\infty} V_i = \left \{\epsilon \right\} \cup V_1 \cup V_2 \cup V_3 \cup \ldots

V* bevat dus alle mogelijke strings met eindige lengte die gegenereerd kunnen worden met symbolen uit V.

Voorbeelden[bewerken]

De Kleene-ster van een verzameling met strings:

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

De Kleene-ster van een verzameling met symbolen:

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}

Generalisatie[bewerken]

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