Kleenesche und positive Hülle

Die kleenesche Hülle (auch endlicher Abschluss, Kleene-*-Abschluss, Verkettungshülle oder Sternhülle genannt) eines Alphabets ${\displaystyle \Sigma }$ oder einer formalen Sprache ${\displaystyle L}$ ist die Menge aller Wörter, die durch beliebige Konkatenation (Verknüpfung) von Symbolen des Alphabets ${\displaystyle \Sigma }$ bzw. von Wörtern der Sprache ${\displaystyle L}$ gebildet werden können, wobei das leere Wort ${\displaystyle \varepsilon }$ inbegriffen ist. Sie ist nach dem US-amerikanischen Mathematiker und Logiker Stephen Cole Kleene benannt. Demgegenüber ist die positive Hülle (auch Kleene-+-Abschluss genannt) eines Alphabets ${\displaystyle \Sigma }$ oder einer formalen Sprache ${\displaystyle L}$ die Menge aller Wörter, die aus den Symbolen von ${\displaystyle \Sigma }$ beziehungsweise aus Wörtern von ${\displaystyle L}$ gebildet werden können und die nur dann das leere Wort enthält, wenn die positive Hülle auf eine Sprache angewandt wird, die selbst das leere Wort als Element enthält.

Der Operator der kleeneschen Hülle ist der Kleene-Stern „${\displaystyle ^{*}}$“. So ist die Darstellung der kleeneschen Hülle eines Alphabets ${\displaystyle \Sigma }$ gleich ${\displaystyle \Sigma ^{*}}$ und einer Sprache ${\displaystyle L}$ gleich ${\displaystyle L^{*}}$. Demgegenüber ist der Operator der positiven Hülle das Pluszeichen „${\displaystyle ^{+}}$“, sodass die positive Hülle eines Alphabets ${\displaystyle \Sigma }$ mit ${\displaystyle \Sigma ^{+}}$ und einer Sprache ${\displaystyle L}$ mit ${\displaystyle L^{+}}$ dargestellt wird.

In Anlehnung a​n den Kleene-*-Operator über Sprachen w​ird der *-Operator b​ei regulären Ausdrücken ebenfalls Kleene-*-Operator genannt. Die Anzahl verschachtelter Kleene-*-Operatoren bestimmt d​ie Sternhöhe e​ines regulären Ausdrucks.

Definition

Hüllenoperator für Alphabete

Die kleenesche Hülle ${\displaystyle \Sigma ^{*}}$ eines Alphabets ${\displaystyle \Sigma }$ ist eine Sprache, die alle Wörter über dem Alphabet enthält. Sie lässt sich mit Hilfe der strukturellen Induktion definieren. Im Induktionsanfang definiert man zunächst, dass das leere Wort ${\displaystyle \varepsilon }$ in der kleeneschen Hülle enthalten ist, und im Induktionsschritt wird definiert, dass für jedes Wort ${\displaystyle w}$, das Element der kleeneschen Hülle ist, auch die Konkatenationen ${\displaystyle w\circ a}$ für alle Symbole ${\displaystyle a\in \Sigma }$ Elemente der Kleeneschen Hülle sind:

• Induktionsanfang: ${\displaystyle \varepsilon \in \Sigma ^{*}}$
• Induktionsschritt: ${\displaystyle (w\in \Sigma ^{*})\land (a\in \Sigma )\Rightarrow w\circ a\in \Sigma ^{*}}$

Die positive Hülle ${\displaystyle \Sigma ^{+}}$ eines Alphabets ${\displaystyle \Sigma }$ ist definiert als die kleenesche Hülle dieses Alphabets ohne das leere Wort:

${\displaystyle \Sigma ^{+}:=\Sigma ^{*}\setminus \{\varepsilon \}}$

Ausgehend von der kleeneschen Hülle lassen sich Teilmengen der Wörter mit fester Länge ${\displaystyle n}$ definieren.

${\displaystyle \Sigma ^{n}:=\{w\mid w\in \Sigma ^{*}\land \left|w\right|=n\}}$

Alternativ kann ${\displaystyle \Sigma ^{n}}$ als das ${\displaystyle n}$-fache kartesische Produkt des Alphabets definiert werden, also

${\displaystyle \Sigma ^{n}=\prod _{i=1}^{n}\Sigma =\underbrace {\Sigma \times \dotsb \times \Sigma } _{n{\text{-mal}}}}$ mit ${\displaystyle \Sigma ^{0}=\{\varepsilon \}}$.

Dann gilt:

${\displaystyle \Sigma ^{*}=\bigcup _{i\in \mathbb {N} _{0}}\Sigma ^{i}}$ und

${\displaystyle \Sigma ^{+}=\bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$

Hüllenoperator für Sprachen

Die kleenesche Hülle ${\displaystyle L^{*}}$ einer Sprache ${\displaystyle L}$ ist die Vereinigung all ihrer Potenzsprachen (wiederholte Konkatenation der Sprachen):

${\displaystyle L^{*}:=\bigcup _{i\in \mathbb {N} _{0}}L^{i}}$

Dabei gilt ${\displaystyle L^{0}=\{\varepsilon \}}$ und ${\displaystyle L^{n+1}=L^{n}\circ L}$.

Die positive Hülle ${\displaystyle L^{+}}$ einer Sprache ${\displaystyle L}$ ist ähnlich definiert, sie ist die Vereinigung aller Potenzen von ${\displaystyle L}$ größer gleich 1:

${\displaystyle L^{+}:=\bigcup _{i\in \mathbb {N} }L^{i}}$

Beispiele

Alphabete

Die kleenesche Hülle des Alphabets ${\displaystyle \Sigma =\{a\}}$ enthält das leere Wort ${\displaystyle \varepsilon }$, das Wort ${\displaystyle \varepsilon \circ a=a}$ und daher auch das Wort ${\displaystyle a\circ a=aa}$ und so weiter. Damit ist

${\displaystyle \Sigma ^{*}=\{\varepsilon ,a,aa,\dotsc \}}$.

Für das Alphabet ${\displaystyle \Sigma =\{a,b\}}$ gilt ${\displaystyle \Sigma ^{2}=\{aa,ab,ba,bb\}}$, ${\displaystyle \Sigma ^{3}=\{aaa,aab,aba,abb,baa,bab,bba,bbb\}}$ und so weiter. Damit ist

${\displaystyle \Sigma ^{*}=\{\varepsilon ,a,b,aa,ab,ba,bb,aaa,aab,aba,\dotsc \}}$.

Sprachen

Die kleenesche Hülle der Sprache ${\displaystyle L=\{aa,bb\}}$ ist die Menge aller Wörter, die sich aus ${\displaystyle aa}$ und ${\displaystyle bb}$ zusammensetzen, sowie dem leeren Wort:

${\displaystyle L^{*}=\{\varepsilon ,aa,bb,aaaa,aabb,bbbb,bbaa,bbaabb,aabbaa,\dotsc \}}$

Die positive Hülle i​st entsprechend:

${\displaystyle L^{+}=\{aa,bb,aaaa,aabb,bbbb,bbaa,bbaabb,aabbaa,\dotsc \}}$

Die kleenesche Hülle d​er leeren Sprache u​nd der Sprache d​es leeren Wortes enthält n​ur das l​eere Wort:

${\displaystyle \{\}^{*}=\{\varepsilon \}^{*}=\{\varepsilon \}}$

Die positive Hülle d​er leeren Sprache i​st leer, d​ie der Sprache d​es leeren Wortes enthält n​ur das l​eere Wort:

${\displaystyle \{\}^{+}=\{\}}$

${\displaystyle \{\varepsilon \}^{+}=\{\varepsilon \}}$

Merkmale

• Die kleenesche Hülle und die positive Hülle (falls letztere das leere Wort enthält) sind jeweils die Trägermenge des Monoids mit der Konkatenation von Wörtern als Operator und dem leeren Wort ${\displaystyle \varepsilon }$ als neutralem Element. So bildet die kleenesche Hülle den freien Monoid über ein Alphabet. Die kleenesche Hülle sowie die positive Hülle sind damit ebenfalls abgeschlossen gegen die Konkatenation.

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

${\displaystyle L\notin \{\{\},\{\varepsilon \}\}\Rightarrow |L^{*}|=|\mathbb {N} |}$

${\displaystyle L\notin \{\{\},\{\varepsilon \}\}\Rightarrow |L^{+}|=|\mathbb {N} |}$

• Wenn eine Sprache ${\displaystyle L}$ das leere Wort enthält, sind die kleenesche und die positive Hülle von ${\displaystyle L}$ identisch; die Umkehrung gilt ebenfalls:

${\displaystyle \varepsilon \in L\Leftrightarrow L^{*}=L^{+}}$

Verallgemeinerungen

Die abzählbar unendlichen Folgen von Zeichen aus dem Alphabet ${\displaystyle \Sigma }$ werden mit ${\displaystyle \Sigma ^{\omega }}$ bezeichnet, siehe: ${\displaystyle \omega }$ = ${\displaystyle \aleph _{0}}$.
${\displaystyle \Sigma ^{\infty }}$ bezeichnet die gesamte Menge ${\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }}$ der endlichen Sequenzen und unendlichen Folgen von Zeichen aus ${\displaystyle \Sigma }$ .

Literatur

• John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3. korrigierte Auflage. Addison-Wesley, Bonn u. a. 1994, ISBN 3-89319-744-3.
• Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer-Verlag, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 27–29.