Die kleenesche Hülle (nach Stephen Cole Kleene) bzw. der endliche Abschluss einer formalen Sprache $\backslash mathbf\{\backslash mathit\{L\}\}$ ist die Menge aller endlichen Wörter (Zeichenketten), die sich durch beliebige Konkatenation von Wörtern der Sprache $\backslash mathbf\{\backslash mathit\{L\}\}$ ergeben, inklusive des leeren Wortes $\backslash mathbf\{\backslash mathit\{\backslash varepsilon\}\}$. Sie wird mit dem Operator $\backslash mathbf\{\backslash mathit$ bezeichnet (dem Kleene-Stern), die Kleenesche Hülle von $\backslash mathbf\{\backslash mathit\{L\}\}$ wird also $\backslash mathbf\{\backslash mathit\{L^*\}\}$ geschrieben. Mathematisch gesprochen ist sie die Trägermenge des Monoids aus den Wörtern der Sprache $\backslash mathbf\{\backslash mathit\{L\}\}$, dem Operator der Konkatenation, und dem neutralen Element $\backslash mathbf\{\backslash mathit\{\backslash varepsilon\}\}$ (leeres Wort).

Die Kleenesche Hülle wird in der Automatentheorie verwendet, um Aussagen über die Eigenschaften von formalen Sprachen zu machen. Wichtig ist dabei vor allem, welche Sprach-Klassen unter Anwendung des Kleene-Sterns abgeschlossen sind. Siehe Abgeschlossenheit bzw. Abgeschlossene Menge.

Definition

---

Die Kleenesche Hülle einer Sprache $L$ bildet sich aus der Vereinigung ihrer Potenzsprachen, d.h.

$L^\backslash star\; :=\; \backslash bigcup\_\{i=0\}^\{\backslash infty\}\; L^i$.

Dabei ist $L^i$ die $i$-te Potenzsprache, es gilt

$L^0\; :=\; \backslash \{\backslash varepsilon\backslash \}$,

$L^\{i+1\}\; :=\; L^i\; \backslash cdot\; L$.

Die positive Hülle ist ähnlich definiert, nur ohne $\backslash mathbf\{\backslash mathit\{L^0\}\}$ sie enthält nur genau dann das leere Wort $\backslash varepsilon$, wenn $L$ es bereits enthält:

$L^+\; :=\; \backslash bigcup\_\{i=1\}^\{\backslash infty\}\; L^i$

Die positive Hülle der leeren Sprache ist leer, die der Sprache des leeren Wortes enthält nur das leere Wort:

$\backslash mathbf\{\backslash mathit\{\backslash \{\backslash \}^+\; =\; \backslash \{\backslash \}\}\}$

$\backslash \{\backslash varepsilon\backslash \}^+\; =\; \backslash \{\backslash varepsilon\backslash \}$

Die Kleenesche und die positive Hülle sind für alle Sprachen, die mindestens ein nicht-leeres Wort enthalten, abzählbar unendlich:

$L\backslash notin\; \backslash \{\backslash \{\backslash \},\; \backslash \{\backslash varepsilon\backslash \}\backslash \}\; \backslash Rightarrow\; |L^\backslash star|\; =\; \backslash aleph\_0$

$L\backslash in\; \backslash \{\backslash \{\backslash \},\; \backslash \{\backslash varepsilon\backslash \}\backslash \}\; \backslash Rightarrow\; L^\backslash star\; =\; \backslash \{\backslash varepsilon\backslash \}\; \backslash Rightarrow\; |L^\backslash star|\; =\; 1$

Beispiel

---

Für die Sprache $\backslash mathbf\{\backslash mathit\{L=\backslash \{aa,\; bb\backslash \}\}\}$ ist die Kleenesche Hülle die Menge aller Wörter, die sich aus „aa“ und „bb“ zusammensetzen lassen, und das leere Wort:

$L^\backslash star=\; \backslash \{\backslash varepsilon,\; aa,\; bb,\; aaaa,\; aabb,\; bbbb,\; bbaa,\; aaaaaa,...\backslash \}$

Die positive Hülle ist entsprechend:

$\backslash mathbf\{\backslash mathit\{L^+=\; \backslash \{aa,\; bb,\; aaaa,\; aabb,\; bbbb,\; bbaa,\; aaaaaa,...\backslash \}\}\}$

Wenn die Sprache $L$ aber selbst das leere Wort enthält, sind die Kleenesche und die positive Hülle gleich: Für $\backslash mathbf\{\backslash mathit\{L=\backslash \{\backslash varepsilon,\; aa,\; bb\backslash \}\}\}$ gilt

$L^+=L^\backslash star=\; \backslash \{\backslash varepsilon,aa,bb,aaaa,aabb,bbbb,bbaa,aaaaaa,...\backslash \}$

Siehe auch

---

• Formale Grammatik
• Regulärer Ausdruck
• Automatentheorie

Literatur

---

• Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, John E. Hopcroft und Jeffry D. Ullman; Addison Wesley, Bonn 1994, ISBN 3-89319-744-3

Theoretische Informatik | Formale Sprachen

Kleene star | Clausura de Kleene | Fermeture de Kleene | Star di Kleene | Domknięcie Kleene'ego | Kleene star