Kleenesche Hülle

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

[Bearbeiten] Definition

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

$L^\star := \bigcup_{i=0}^{\infty} L^i$ .

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

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

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

Die positive Hülle ist ähnlich definiert, nur ohne $\mathbf{\mathit{L^0}}$ sie enthält nur genau dann das leere Wort $\varepsilon$ , wenn $L$ es 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:

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

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

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

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

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

[Bearbeiten] Beispiel

Für die Sprache $\mathbf{\mathit{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^\star= \{\varepsilon, aa, bb, aaaa, aabb, bbbb, bbaa, aaaaaa,...\}$

Die positive Hülle ist entsprechend:

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

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

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

[Bearbeiten] Siehe auch

[Bearbeiten] 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

Von „http://de.wikipedia.org../../../k/l/e/Kleenesche_H%C3%BClle_b6a1.html“

Kategorien: Theoretische Informatik | Formale Sprachen