Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Kleenescher Abschluss

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Kleenescher Abschluss

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Nunzio
Jungspund

Dabei seit: 18.04.2013
Beiträge: 13

Kleenescher Abschluss

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Hallo, ich habe eine Frage zur folgenden Aufgabe aus meinem Skript :

W1.1 (Kleenescher Abschluss)
Beweisen oder widerlegen sie ausführlich : Für jede Sprache L mit epsilon(das leere Wort) ist nicht Element aus L gilt L*/L+ = epsilon

Meine Ideen:
Also ich hab folgende Vermutung. Ich denke es stimmt nicht, da :

L* alle Konkatenationen von null oder mehr Wörtern aus L darstellt und
L+ alle Konkatenationen von einem oder mehr Wörtern aus L darstellt.

Also ist die Differenz von L* und L+ doch die leere Sprache und nicht das leere Wort, oder sehe ich das falsch? Seit bitte nicht so hart mit mir, das war die erste Vorlesungsstunde :P

Vielen Dank im Vorraus

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Nunzio: 18.04.2013 13:14.

18.04.2013 13:10

Nehmen Sie Nunzio in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo,

leider stimmt deine Definition von $[latex]\mathcal{L}^*[/latex]$ und $[latex]\mathcal{L}^+[/latex]$ nicht. Bitte Suche noch einmal die Defintion von $[latex]\mathcal{L}^*[/latex]$ und $[latex]\mathcal{L}^+[/latex]$ heraus und versuche den Beweis anhand der Defintion. Gern helfe ich dir dann weiter.

Bitte noch ergänzend folgende Fragen beantworten:
Sei $[latex]\mathcal{L}=\{aa,b\}[/latex]$ . Was ist dann $[latex]\mathcal{L}^0[/latex]$ , $[latex]\mathcal{L}^1[/latex]$ und $[latex]\mathcal{L}^2[/latex]$ ?

Edit: Es reicht wenn Du erstmal nur die Definition aufschreibtst und die Frage beantwortest.

VG,

Karlito

18.04.2013 14:19

Nehmen Sie Karlito in Ihre Freundesliste auf

Nunzio
Jungspund

Dabei seit: 18.04.2013
Beiträge: 13

Hallo Karlito,

danke für deine schnelle Antwort.

Nun gut, ich schreibe jetzt die Definition aus dem Buch von Uwe Schöningh "theoretische Informatik - kurz gefasst" ab.

Für ein gegebenes Alphabet Sigma bezeichne Sigma* die Menge aller Wörter, die sich durch Konkatenation von Symbolen aus Sigma bilden lassen. DIes ist nichts anderes als die Menge aller endlichen Folgen von Elementen aus Sigma. DIes schließt auch die leere Folge, bzw. das leere Wort ein, welches wir mit epsilon beschreiben.

Mit Sigma+ bezeichnen wir Sigma* - {epsilon}

Nunja, ich würde immer noch sagen, das dort die leere Sprache herauskommt, weil das epsilon ja durch die Annahme gestrichen wurde...

Leider kann ich deine zusätzlichen Fragen nicht beantworten. Ich verstehe nicht was ich da nun machen soll unglücklich

mfg Nunzio

21.04.2013 20:47

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Schau dir mal die Definition auf Wikipedia an.

Demnach ist ja

$[latex]L^* := \bigcup_{i\in\mathbb N_0} L^i[/latex]$ ,
$[latex]L^+ := \bigcup_{i\in\mathbb N} L^i[/latex]$
und es gilt $[latex]L^0=\{\varepsilon\}[/latex]$ und $[latex]L^{n+1}=L^n\circ L[/latex]$ .

$[latex]L \circ L[/latex]$ ist die Konkatenation einer Sprache mit sich selbst. D.h. jedes Wort der Sprache wird mti jedem Wort der Sprache konkateniert und die Menge der Wörter die dabei entsteht ist die Sprache $[latex]L^{2}[/latex]$ .

Damit solltest Du eigentlich in der Lage sein, alle Fragen zu beantworten.

Wie sieht daher $[latex]L^+ \cap L^*[/latex]$ aus? Die leere Sprache ist es nicht.

VG,

Karlito

22.04.2013 14:52

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Kleenescher Abschluss