Kleenesche und positive Hülle

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

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 bildet sich aus der Vereinigung aller Potenzsprachen der Sprache L, also

L^{*}=\bigcup _{i=0}^{\infty }L^{i}

dabei ist $L^{i}$ die i-te Potenzsprache, und es gilt

L^{0}=\{\epsilon \}

,

L^{1}=L

,

L^{2}=L\times L

, usw.

Die Kleenesche Hülle (und auch die positive Hülle) ist für alle Sprachen, die mindestens ein nicht-leeres Wort enthalten, unendlich groß:

L\notin \{\{\},\{\epsilon \}\}\Rightarrow |L^{*}|=\infty

L\in \{\{\},\{\epsilon \}\}\Rightarrow L^{*}=\{\epsilon \}\Rightarrow |L^{*}|=1

Die positive Hülle ist fast genau so definiert, nur ohne $L^{0}$ : sie enthält deshalb das leere Wort ε nicht, wenn L es nicht bereits enthält:

L^{+}=\bigcup _{i=1}^{\infty }L^{i}

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

\{\}^{+}=\{\}

\{\epsilon \}^{+}=\{\epsilon \}

Beispiel

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

$L^{*}=\{\epsilon ,aa,bb,aaaa,aabb,bbbb,bbaa,aaaaaa,...\}$

die positive Hülle ist entsprechend:

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

Wenn die Sprache L aber selbst das leere Wort enhält, sind der endliche und der positive Abschluss gleich: Für L={ε,aa,bb} gilt

$L^{+}=L^{*}=\{\epsilon ,aa,bb,aaaa,aabb,bbbb,bbaa,aaaaaa,...\}$

Siehe auch

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