Welche Sprache erzeugt diese Grammatik - Seite 2

10.12.2006, 18:48

Tobias

Nein, nicht wenn das leere Wort schon in L drin ist.

Mache dir das klar:

$[latex]\epsilon \in L \iff \epsilon \in L^+[/latex]$

Beweis:

$[latex] \Rightarrow [/latex]$
Wegen $[latex]\epsilon \in L[/latex]$ und $[latex]L \subseteq L^+[/latex]$ gilt auch $[latex]\epsilon \in L^+[/latex]$

$[latex] \Leftarrow [/latex]$
Seien M und N zwei Sprachen, dann ist das leere Wort in MN nur dann, wenn es sowohl in M als auch in N ist.

Sei $[latex]\epsilon \in L^+[/latex]$ also in mindestens einem [latex]L^i[/latex]

für $[latex]i \geq 1[/latex]$ . Für i=1 ist der Fall klar. Für i>1 gilt:
$[latex]L^i = LL^{i-1}[/latex]$ und somit greift der Satz von oben.

10.12.2006, 19:29

Auf diesen Beitrag antworten »

Asgard

Ist hier nicht ein Widerspruch?

Zitat:

Original von Tobias
$[latex] \Leftarrow [/latex]$
Seien M und N zwei Sprachen, dann ist das leere Wort in MN nur dann, wenn es sowohl in M als auch in N ist.

Sei $[latex]\epsilon \in L^+[/latex]$ also in mindestens einem [latex]L^i[/latex]

für $[latex]i \geq 1[/latex]$ . Für i=1 ist der Fall klar. Für i>1 gilt:
$[latex]L^i = LL^{i-1}[/latex]$ und somit greift der Satz von oben.

Auf der einen Seite ist $[latex]\epsilon \in MN[/latex]$ wenn $[latex]\epsilon \in M[/latex]$ und $[latex]\epsilon \in N[/latex]$ .

Auf der anderen Seite ist aber $[latex]\epsilon \in L^{n}=LL^{n-1}[/latex]$ , wenn $[latex]\epsilon[/latex]$ in mindestens einem $[latex]L^{i}[/latex]$ für n>0 ist. Somit könnte doch durchaus ein $[latex]L^{i}~mit~\epsilon \not\in L^{i}[/latex]$ existieren.

Auch steht im Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning Folgendes:

Zitat:

Mit $[latex]{\sum}^{+}[/latex]$ bezeichnen wir $[latex]{\sum}^{*} - \{\epsilon\}[/latex]$

EDIT: Wie menschlich das Versagen! Mein Fehler liegt darin, dass alles was ich meine, auf Alphabete bezogen ist und nicht auf Sprachen.

10.12.2006, 19:41

Auf diesen Beitrag antworten »

Tobias

Das ist kein Widerspruch, denn ich sagte es muss in mindestens einem L^i drin sein. Das schließt nicht aus, dass es in allen L^i drin ist.

Ich nehme die Definition:

$[latex]L^+ = L L^1 L^2 L^3 \ldots L^i \ldots[/latex]$

Jetzt muss das leere Wort ja irgendwo hergekommen sein. Also laut erster naiver Annahme aus mindestens einer der Menge L^i. Das schließt weder aus, dass es in allen drin sein kann noch schließt es aus, dass es in einem L^j nicht drin ist.

Dann kommt das nächste Argument...

10.12.2006, 21:15

Auf diesen Beitrag antworten »

Asgard

Ich verstehe nur Folgendes nicht so ganz:

Zitat:

Seien M und N zwei Sprachen, dann ist das leere Wort in MN nur dann, wenn es sowohl in M als auch in N ist.

Wenn nun also $[latex]\epsilon \in L^{+}[/latex]$ , so müsste dann doch auch $[latex]\epsilon \in L^{i}[/latex]$ für jedes $[latex]i \geq 1[/latex]$ gelten, da doch laut obiger Aussage das leere Wort in der Konkatenation zweier Sprachen liegt, wenn es in beiden Sprachen vorhanden ist. Wo ist hier mein Denkfehler?

10.12.2006, 21:44

Auf diesen Beitrag antworten »

Tobias

Das ist kein Denkfehler, das ist richtig.

Nochmal mein Argument:

Wenn M und N beliebige Mengen sind, dann kann man sagen: $[latex]x \in M \cup N \iff x \in M \vee x \in N[/latex]$

Das erweitern wir auf $[latex]L^+ = \bigcup_{n \geq 1} L^n[/latex]$ .

$[latex]x \in L^+ \iff x \in L^i \text{ fuer ein } i \geq 1[/latex]$

Wo siehst du nun einen Widerspruch?

10.12.2006, 22:11

Auf diesen Beitrag antworten »

Asgard

Jetzt sehe ich ihn nicht mehr, aber Du veränderst auch gerade Deine Aussagen Augenzwinkern

Zitat:

$[latex]\epsilon \in L \iff \epsilon \in L^+[/latex]$

...

$[latex]x \in L^+ \iff x \in L^i \text{ fuer ein } i \geq 1[/latex]$

Zitat:

Seien M und N zwei Sprachen, dann ist das leere Wort in MN nur dann, wenn es sowohl in M als auch in N ist.

...

Wenn M und N beliebige Mengen sind, dann kann man sagen: $[latex]x \in M \cup N \iff x \in M \vee x \in N[/latex]$

Jetzt bin ich verwirrt großes Grinsen

Doch so langsam kommt die Erleuchtung auf simplem Wege:
Aus $[latex]L^{+} = L^{*}L[/latex]$ folgt ja eigentlich, dass $[latex]\epsilon \in L^{+}[/latex]$ , für den Fall, dass $[latex]\epsilon \in L[/latex]$ .

10.12.2006, 22:32

Auf diesen Beitrag antworten »

Tobias

Ich glaube dich hat die Reihenfolge meines "Hilfssatzes" negativ beeinflusst. Augenzwinkern

Meine Argumentationskette ist eigentlich:

Voraussetzung: Leeres Wort ist in L^+

zu zeigen: Leeres Wort ist in L

1. Schritt: Es gibt es ein L^i, so dass leeres Wort in L^i ist
2.1 Schritt: Wenn i=1 ist alles gezeigt.
2.2 Schritt: Wenn i>1 ist leeres Wort in LL^(i-1). <-- hier meinen Satz über M und N anwenden

10.12.2006, 23:49

Auf diesen Beitrag antworten »

Asgard

Jetzt ist das Licht endlich aufgegangen. Vielen Dank für Deine Geduld.

vorherige Seite

Neue Frage »

Antworten »

Welche Sprache erzeugt diese Grammatik - Seite 2

Verwandte Themen