Informatiker Board | formale Sprachen

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Positive Hülle

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Positive Hülle

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

MauroG
Grünschnabel

Dabei seit: 04.11.2013
Beiträge: 1

Positive Hülle

Zitatantwort auf diesen Beitrag erstellen

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

04.11.2013 18:10

Nehmen Sie MauroG in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

05.11.2013 10:29

Nehmen Sie Karlito in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Positive Hülle