Moin moin,

auch nach mehrmaligem Lesen der Aufgabe ist mir irgendwie nicht ganz klar was da gemacht werden soll.
Vermutlich sehe ich mal wieder den Baum vor Wäldern nicht aber kann mir mal jemand nen Tip geben was dort gefordert ist?

Gruß,

Pelle

auch nach mehrmaligem Lesen der Aufgabe ist mir irgendwie nicht ganz klar was da gemacht werden soll.
Vermutlich sehe ich mal wieder den Baum vor Wäldern nicht aber kann mir mal jemand nen Tip geben was dort gefordert ist?

Nun das steht doch da:

[img]http://mokrates.de/cgi-bin/texstring?%5C%5B%5C%5DDamit%20Sie%20nicht%20lange%20z%22ogern,%20versichern%20Ihnen%20alle%20%22Ubungsgruppenleiter,%0Adass%20auch%20mit%20dieser%20neuen%20Akzeptierungsvariante%20genau%20die%20regul%22aren%20Mengen%0Aakzeptiert%20werden!%20%5C%5C%0A%0A%0ADass%20f%22ur%20jeden%20vDFA%20$B$%20stets%20$L(B)%20=L_%7Bneu%7D(B)$%20gilt,%20ist%20leicht%20zu%20sehen!%20Beweisen%0ASie%20die%20Aussage%20nun,%20indem%20Sie%20jetzt%20noch%20zu%20einem%20beliebigen%20NFA%20$A$%20einen%20endlichen%0AAutomaten%20$B$%20konstruieren,%20f%22ur%20den%20$L_%7B(B)%7D%20=%20L_%7Bneu%7D(A)$%20ist,%20wobei%20f%22ur%20$B$%0Anat%22urlich%20die%20im%20Skript%20stehende%20Definition%20von%20$L(B)$%20benutzt%20werden%20soll.[/img]

Also die Aussage
"Mit der neuen Akzeptierungsvorschrift werden genau die regulären Mengen akzeptiert"
soll bewiesen werden

Die einfache Richtung, s.o. war schon formliert:
"Mit der neuen Akzeptierungsvorschrift wird jede reguläre Menge akzeptiert!"
Das steht halt nicht so ausgeschrieben dort!

Also fehlt noch (und das ist also die Aufgabe!):
"Alles was mit der neuen Vorschrift als [img]http://mokrates.de/cgi-bin/texstring?$L_%7Bneu%7D(A)$[/img] akzeptiert wird ist regulär,
kann also von einem endl. Automaten nach üblicher Vorschrift für L(B) akzeptiert werden!

Hoffentlich hilfts, denn was nun folgen sollte, schreib ich nicht aus…

Also die Aussage
"Mit der neuen Akzeptierungsvorschrift werden genau die regulären Mengen akzeptiert"
soll bewiesen werden

Die einfache Richtung, s.o. war schon formliert:
"Mit der neuen Akzeptierungsvorschrift wird jede reguläre Menge akzeptiert!"
Das steht halt nicht so ausgeschrieben dort!

Und wie/wo setze ich da an? In der Aufgabenstellung steht ja, dass man zu einem beliebigen endlichen Automaten A einen Automaten B konstruieren soll, für den L(B)=Lneu(A) gilt. Wieso ist das dann ein Beweis der Aussage?

Wo ist dieser L(B) im Skript denn aufgeführt, mit dem man da arbeiten soll? Vielleicht habe ich auch noch nicht lange genug auf die Aufgabenstellung gestarrt, aber wirklich viel konnte ich da bis jetzt nicht daraus lesen.

In der Aufgabenstellung steht ja, dass man zu einem beliebigen endlichen Automaten A einen Automaten B konstruieren soll, für den L(B)=Lneu(A) gilt. Wieso ist das dann ein Beweis der Aussage?

Die fehlende Richtung ist doch, dass jede Sprache, die als
[img]http://mokrates.de/cgi-bin/texstring?L_%7Bneu%7D(A)[/img] mit einem endlichen Automaten A geschrieben
werden kann, auch regulär ist. Und wie zeigt man z.B., dass
eine Sprache regulär ist? Na, ganz einfach: man gibt einen
endlichen Automaten an, der die Sprache akzeptiert, d.h.
in diesem Fall einen endlichen Automaten B mit [img]http://mokrates.de/cgi-bin/texstring?L(B)%3DL_%7Bneu%7D(A)[/img].
Denn eine Sprache ist ja regulär genau dann, wenn sie von
einem endlichen Automaten akzeptiert werden kann.

Wo ist dieser L(B) im Skript denn aufgeführt, mit dem man da arbeiten soll?

Mit "Definition von L(B)" ist hier eigentlich die Definition
der akzeptierten Sprache von endlichen Automaten gemeint. Damit
wird nur nocheinmal wiederholt, dass für den von dir
angegebenen Automaten B wirklich [img]http://mokrates.de/cgi-bin/texstring?L(B)%3DL_%7Bneu%7D(A)[/img]
gelten soll und nicht etwa [img]http://mokrates.de/cgi-bin/texstring?L_%7Bneu%7D(B)%3DL_%7Bneu%7D(A)[/img].

Und wie zeigt man z.B., dass
eine Sprache regulär ist? Na, ganz einfach: man gibt einen
endlichen Automaten an, der die Sprache akzeptiert, d.h.
in diesem Fall einen endlichen Automaten B mit [img]http://mokrates.de/cgi-bin/texstring?L(B)%3DL_%7Bneu%7D(A)[/img].
Denn eine Sprache ist ja regulär genau dann, wenn sie von
einem endlichen Automaten akzeptiert werden kann.

D.h. aber, dass ich mir nicht irgendeinen Automaten ausdenke und das für diesen Automaten zeige, sondern das ganze formal für beliebige endliche Automaten zeige, oder? Danke übrigens für deine Mühe…

D.h. aber, dass ich mir nicht irgendeinen Automaten ausdenke und das für diesen Automaten zeige, sondern das ganze formal für beliebige endliche Automaten zeige, oder? Danke übrigens für deine Mühe…

Du musst einen Automaten B angeben, der die Sprache [img]http://mokrates.de/cgi-bin/texstring?L_%7Bneu%7D(A)[/img]
akzeptiert. Den musst du dir also gewissermaßen ausdenken.
Das ganze musst du aber für beliebige Automaten A machen.

Wo ist dieser L(B) im Skript denn aufgeführt, mit dem man da arbeiten soll?

Mit "Definition von L(B)" ist hier eigentlich die Definition
der akzeptierten Sprache von endlichen Automaten gemeint. Damit
wird nur nocheinmal wiederholt, dass für den von dir
angegebenen Automaten B wirklich [img]http://mokrates.de/cgi-bin/texstring?L(B)%3DL_%7Bneu%7D(A)[/img]
gelten soll und nicht etwa [img]http://mokrates.de/cgi-bin/texstring?L_%7Bneu%7D(B)%3DL_%7Bneu%7D(A)[/img].

Wenn aber gilt L(B)=Lneu(B) das soll ja ganz einfach zu sehen sein.
Und man soll zeigen, daß L(B)=Lneu(A) ist. Dann ist es das gleiche, als wenn man zeigen würde, dass Lneu(B)=Lneu(A) ist. Dies finde ich etwas seltsam, da man doch weiß, daß man jeden NFA als DFA darstellen kann und es gilt L(DFA)=L(NFA). Was soll man da wirklich Beweisen????

Also die Beiden definitionen sind doch gleich, bis auf das bei der neuen nur Alle endzustände die über die Wörter zu finden sind aufzuschreieb sind als Erfolgspfad. Das ändert doch an den Worten garnichts ob man nun einen oder alle endzustände die dieses Wort zum akzeptieren führen ???? Was soll man da bitte Beweisen?

D.h. aber, dass ich mir nicht irgendeinen Automaten ausdenke und das für diesen Automaten zeige, sondern das ganze formal für beliebige endliche Automaten zeige, oder? Danke übrigens für deine Mühe…

Du musst einen Automaten B angeben, der die Sprache [img]http://mokrates.de/cgi-bin/texstring?L_%7Bneu%7D(A)[/img]
akzeptiert. Den musst du dir also gewissermaßen ausdenken.
Das ganze musst du aber für beliebige Automaten A machen.

Hm, nochmal ne Frage, auf dem Übungsblatt steht: "Dass für jeden vDFA B stets L(B) = Lneu(B) gilt, ist leicht zu sehen!"
Darf ich das dann als feststehende Aussage verwenden, oder muss ich das beweisen?

Connor:

Wenn aber gilt L(B)=Lneu(B) das soll ja ganz einfach zu sehen sein.

Nein, dort steht nur, dass [img]http://mokrates.de/cgi-bin/texstring?L(B)%3DL_%7Bneu%7D(B)[/img] gilt,
wenn B ein vDFA ist. Im Allgemeinen gilt das natürlich nicht!

Connor:

Das ändert doch an den Worten garnichts ob man nun einen oder alle endzustände die dieses Wort zum akzeptieren führen ????

Das ändert natürlich die akzeptierte Sprache. Jedes Wort w, das
über die neue Vorschrift akzeptiert wird, wird auch über die alte
akzeptiert, denn wenn die Menge aller Zustände, in die man mit
diesem Wort kommt, nur aus Endzuständen besteht und nicht leer ist,
gibt es auch (mindestens) eine Rechnung, die in einem Endzustand
landet. D.h. es gilt immer [img]http://mokrates.de/cgi-bin/texstring?L_%7Bneu%7D(A)%5Csubseteq%20L(A)[/img].

Die andere Inklusion [img]http://mokrates.de/cgi-bin/texstring?L(A)%5Csubseteq%20L_%7Bneu%7D(A)[/img] gilt dagegen nicht für alle
Automaten A! Denn es kann z.B. sein, dass es für ein w aus L(A) eine
Rechnung gibt, die in einem Endzustand von A landet und eine andere
Rechnung, die in einem Zustand landet, der kein Endzustand ist. Dann
liegt w nicht in [img]http://mokrates.de/cgi-bin/texstring?L_%7Bneu%7D(A)[/img], denn schließlich führt nicht jede Rechnung
zu w in einen Endzustand.