Informatiker Board | Druckvorschau: Positive Hülle

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Positive Hülle (http://www.informatikerboard.de/board/thread.php?threadid=1688)

Geschrieben von MauroG am 04.11.2013 um 18:10:

Positive Hülle

Hallo zusammen,

ich hoffe es ist jemand da und kann mir bei folgenden Aufgaben helfen:

Sei $[latex]L \subseteq \Sigma^{\star} [/latex]$ eine beliebige Sprache. Es sei ferner $[latex]$ L^{+}:=\{x_1x_2...x_k|k \ge 1,x_i \in L\} $[/latex]$ .

Aufgabe 1:
Für welche Sprache [latex]$ L $[/latex]

ist $[latex]$ L^{+} $[/latex]$ leer? Begründen Sie Ihre Antwort.

Aufgabe 2:
Für welche Sprache [latex]$ L $[/latex]

ist $[latex]$ L^{+} $[/latex]$ endlich? Geben Sie jeweils [latex]$ L $[/latex]

und $[latex]$ L^{+} $[/latex]$ an und begründen Sie Ihre Antwort.

Mein bisheriger Lösungsansatz:
Aufgabe 1:
Für $[latex]L:=\{\varepsilon\}[/latex]$ ist [latex]L^+[/latex]

leer, da das $[latex]\varepsilon[/latex]$ nicht zu [latex]L^+[/latex]

dazugehört ist [latex]L^+[/latex]

leer und endlich.

Aufgabe 2:
Für folgende Sprachen ist [latex]L^+[/latex]

endlich:
$[latex]L:=\emptyset[/latex]$ und $[latex]L:=\{\varepsilon\}[/latex]$
Da bei diesen Sprachen keine Wörter gebildet werden können, sieht [latex]L^+[/latex]

so aus: $[latex]L^+:=\emptyset[/latex]$
Im Falle $[latex]L:=\{\varepsilon\}[/latex]$ gilt $[latex]L^+:=\emptyset[/latex]$ , da gilt $[latex]k \ge 1[/latex]$ wobei $[latex] w \in \Sigma^*[/latex]$ gilt und [latex]k=|w|[/latex]

.
Im Falle $[latex]L:=\emptyset[/latex]$ ist auch $[latex]L^+:=\emptyset[/latex]$ , da man mit einer leeren Sprache keine Wörter bilden kann.

Ist das soweit richtig bzw. ist auch die Erklärung plausibel?

Vielen Dank im voraus und viele Grüße

Geschrieben von Karlito am 05.11.2013 um 10:29:

Hallo MauroG,

du begehst einen großen Fehler: Das leere Wort ist ein Wort! D.h. für $[latex]L = \{\epsilon\}[/latex]$ exisitert ein Wort $[latex]x = \epsilon[/latex]$ und somit besteht die Sprache [latex]L^+[/latex]

aus allen möglichen Konkatenationen von $[latex]\epsilon[/latex]$ mit sich selbst. Also $[latex]L^+ = \{\epsilon\}[/latex]$

Die Verwirrung stammt vielleicht aus einer Definition von $[latex]\Sigma^+[/latex]$ , da $[latex]\Sigma^+ := \Sigma^* \setminus \{ \epsilon \}[/latex]$ . Diese Definition kann man jedoch nur so schreiben, weil $[latex]\Sigma^+ := \bigcup^{\infty}_{i=1}\Sigma^i = \left( \bigcup^{\infty}_{i=0}\Sigma^i \right) \setminus \Sigma^0 [/latex]$ und $[latex]\Sigma^0[/latex]$ ist die einzige möglichkeit wie das leere Wort entstehen kann.

Bei [latex]L^1[/latex]

kann jedoch das leere Wort bereits enthalten sein und kann [latex]L^+[/latex]

nicht als $[latex]L^+ := L^* \setminus {\epsilon}[/latex]$ dargestellt werden.

Gruß,

Karlito