Informatiker Board | Theoretische Informatik | Welche Sprache erzeugt diese Grammatik

Informatiker Board » Themengebiete » Theoretische Informatik » Welche Sprache erzeugt diese Grammatik » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 10 Beiträge

Asgard

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

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

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]$ .

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?

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?

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...

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.

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.

Asgard

Entweder verstehe ich Dich falsch, oder in unserer Vorlesung wurde etwas anderes gelehrt.

Für $[latex]L \subseteq {\sum}^{*}[/latex]$ sei

$[latex]L^{*} = \bigcup_{n\geq 0} L^{n} = \{w_1 ... w_n | n\geq 0, w_i \in L~fuer~i=1,...,n \}[/latex]$ der Kleene-Abschluss von L.
$[latex]L^{+} = \bigcup_{n\geq 1} L^{n} = \{w_1 ... w_n | n\geq 1, w_i \in L~fuer~i=1,...,n \} = LL^{*}[/latex]$

Folgerung: $[latex]L^{*} = L^{+} \cup L^{0} = L^{+} \cup \{\epsilon\}[/latex]$

Laut dieser Definition würde doch $[latex]L^{+}[/latex]$ das leere Wort bei einer Sprache ausschließen?!?

Tobias

$[latex]L^\ast[/latex]$ für eine Sprache L ist die "Kleenesche Hülle". Diese ist natürlich ein freies Monoid bezüglich der Konkatenation weil $[latex]\epsilon \in L^\ast[/latex]$ das neutrale Element und L der Erzeuger des Monoids ist.

[latex]L^+[/latex]

ist die positive Hülle und nicht immer ein Monoid. Insbesondere gilt $[latex]\epsilon \in L^+ \iff \epsilon \in L[/latex]$

Die positive Hülle ist nicht unbedingt die Menge der nichtleeren Wörter. Das gilt nur dann, wenn die Basismenge das leere Wort nicht enthält.

Für alle Sprachen L mit $[latex]\epsilon \in L[/latex]$ gilt $[latex]L^+ = L^\ast[/latex]$ .

Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen.