Kleenesche und positive Hülle

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}}$

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}}$

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 \}}$.

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 ist entsprechend:

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

Die kleenesche Hülle der leeren Sprache und der Sprache des leeren Wortes enthält nur das leere Wort:

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

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

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

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