FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Unterbereich Grundstudium / Formale Informatik

F2 Beweis für L^* e Akz(Sigma) aus Folie ?

F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-17 13:49
Anonymer User
[img]http://img140.imageshack.us/img140/5172/abstern3au.jpg[/img]

versteh die Konstruktion mit K1, K2, K3 nicht,
kann das jemand anhand eines Beispiels vorführen?

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-17 14:48
georg
Ich versuche es mal zu erklären.
Zunächst sollte es wohl
[img]http://mokrates.de/cgi-bin/texstring?K_1%3D%5C%7B(z%2Cx%2C%5Cdelta(z%2Cx))%5Cmid%20z%5Cin%20Z%2C%20x%5Cin%5CSigma%5C%7D[/img]
heißen. Zu K1 steht ja schon dabei: das sind die Kanten, die
auch in A schon enthalten sind. Die Kanten in K2 und K3
beschreiben nun die Kanten, die im neuen Zustand p anfangen
oder enden. Die Kanten in K2 sorgen dafür, dass auf Symbole,
die in p gelesen werden, so reagiert wird, als wären sie in
z0 gelesen worden (man kommt in den gleichen Zustand,
in den man von z0 aus gekommen wäre). Und in K3 kommen die
Kanten hinzu, die den Automaten in den Zustand p gehen lassen,
wenn er ohne die neuen Kanten auch in einen Endzustand hätte
gehen können. Damit werden alle Wörter aus L* akzeptiert
(denn wenn w aus L von A akzeptiert wird, gibt es in [img]http://mokrates.de/cgi-bin/texstring?C_%7BA%5E*%7D[/img] eine Rechnung,
die in p endet und von dieser aus kann man (weil p sich wie z0
verhält) wieder ein Wort aus L akzeptieren, etwa v aus L, und hat
insgesamt uv akzeptiert, usw.). Also [img]http://mokrates.de/cgi-bin/texstring?L%5E*%5Csubseteq%20L(C_%7BA%5E*%7D)[/img].
Und wenn umgekehrt ein Wort w im neuen Automaten akzeptiert
wird, besitzt es eine Zerlegung in Wörter aus L, denn man
kann w an den Stellen auftrennen, an denen der Zustand p erreicht
wird und diese Teilwörter liegen in L (weil für sie nur Kanten
benutzt wurden, die bereits in A waren), also liegt w in L*.
Also [img]http://mokrates.de/cgi-bin/texstring?L(C_%7BA%5E*%7D)%3DL%5E*[/img].

Ist das damit klar geworden?

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-17 17:57
Anonymer User
Nicht ganz, also man hat den vDFA

http://img145.imageshack.us/img145/553/vdfabeispieldea3wi.jpg

Nun fügt man einen neuen Zustand P ein
(ich weiss wie man K2 anwendet aber K3? )

[img]http://img145.imageshack.us/img145/4605/1schrittzbnfadea6tn.jpg[/img]

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-17 19:23
Anonymer User
wie gehts jetzt weiter?

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-17 20:38
georg
Das steht doch in der Definition: für jedes Paar
[img]http://mokrates.de/cgi-bin/texstring?(z%2Cx)%5Cin%20Z%5Ctimes%20%5CSigma[/img], für das [img]http://mokrates.de/cgi-bin/texstring?%5Cdelta(z%2Cx)[/img] ein Endzustand
ist, fügst du die Kante (z,x,p) hinzu. Oder anders
formuliert: jede Kante, die in einem Endzustand
endet, wird einmal kopiert und nach p "umgebogen".

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-17 20:49
Anonymer User
Also:

[img]http://img138.imageshack.us/img138/5084/2schrittzbnfadea1sj.jpg[/img]

oder?

und dann?

(sorry, wenn ich mit meinen Fragen nerve..)

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 12:08
theorinix
Also:

[img]http://img138.imageshack.us/img138/5084/2schrittzbnfadea1sj.jpg[/img]

oder?

und dann?

(sorry, wenn ich mit meinen Fragen nerve..)

Umbiegen der Kante (z_1,b,z_2) meint hier aber NICHT Entfernen!
Alle alten Kanten bleiben erhalten, es kommen mit K_2 und K_3 nur neue hinzu!!

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 14:17
Anonymer User
hier nochmal ein Versuch

vDFA:

http://img208.imageshack.us/img208/1296/beispieldeadea0yr.jpg

bNFA:

http://img235.imageshack.us/img235/560/bneanea6df.jpg

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 15:46
Anonymer User
^
|_[richtig]?

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 16:16
georg
Also dann sehe ich es mir mal an.

hier nochmal ein Versuch

vDFA:

http://img208.imageshack.us/img208/1296/beispieldeadea0yr.jpg

bNFA:

http://img235.imageshack.us/img235/560/bneanea6df.jpg

Wenn ich die zweite Grafik richtig verstehe, gibt es da eine Kante
(z1, a, p). Die muss in (p, a, z1) geändert werden (ist in K2).
Außerdem müssen die Kanten (z2, a, p) und (z2, b, p) hinzugefügt
werden (sind in K3). Und schließlich muss p noch zum Start- und
zum einzigen Endzustand gemacht werden. Ansonsten sehe ich
keine Fehler.

Übrigens gibt es eine viel schnellere Variante, einen NFA
für L* zu finden: Eine lambda-Kante von jedem Endzustand
zum Startzustand (das kam im letzten Jahr auch in der
Vorlesung vor). Der ist dann allerdings nicht buchstabierend.

Und manchmal spart es Arbeit, wenn man sich die bisher
akzeptierte Sprache ansieht: bei deinem letzten Beispiel
hätte es auch genügt, z0 zu einem Endzustand zu machen.

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 16:37
Anonymer User
Wenn ich die zweite Grafik richtig verstehe, gibt es da eine Kante
(z1, a, p). Die muss in (p, a, z1) geändert werden (ist in K2).
Das ist nur ein seltsamer Grafikfehler - manchmal geht eine Pfeilspitze verloren..
Außerdem müssen die Kanten (z2, a, p) und (z2, b, p) hinzugefügt
werden (sind in K3). Und schließlich muss p noch zum Start- und
zum einzigen Endzustand gemacht werden.
Übrigens gibt es eine viel schnellere Variante, einen NFA
für L* zu finden: Eine lambda-Kante von jedem Endzustand
zum Startzustand (das kam im letzten Jahr auch in der
Vorlesung vor). Der ist dann allerdings nicht buchstabierend.
Hör ich zum ersten Mal, aber ich schlaf in den Vorlesungen auch schnell ein.. [img]http://www.fb18.de/gfx/24.gif[/img]
Und manchmal spart es Arbeit, wenn man sich die bisher
akzeptierte Sprache ansieht: bei deinem letzten Beispiel
hätte es auch genügt, z0 zu einem Endzustand zu machen.
Warum das ? Der Anfangs vDFA akzeptiert nur wenn mind ein b da ist?

Hier der bNFA v.2.0
http://img147.imageshack.us/img147/986/bneanea7zz.jpg

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 16:50
georg
Und manchmal spart es Arbeit, wenn man sich die bisher
akzeptierte Sprache ansieht: bei deinem letzten Beispiel
h�tte es auch gen�gt, z0 zu einem Endzustand zu machen.
Warum das ? Der Anfangs vDFA akzeptiert nur wenn mind ein b da ist?

Richtig, [img]http://mokrates.de/cgi-bin/texstring?L%3D%5C%7Bw%5Cin%5C%7Ba%2Cb%5C%7D%5E*%5Cmid%20%7Cw%7C_b%5Cge%201%5C%7D[/img].
Dann überlegt man sich leicht [img]http://mokrates.de/cgi-bin/texstring?L%5E%2B%5Csubseteq%20L[/img], also
[img]http://mokrates.de/cgi-bin/texstring?L%5E%2B%3DL[/img] und damit [img]http://mokrates.de/cgi-bin/texstring?L%5E*%3DL%5E%2B%5Ccup%5C%7B%5Clambda%5C%7D%3DL%5Ccup%5C%7B%5Clambda%5C%7D[/img],
d.h. man muss nur das leere Wort hinzufügen.

Hier der bNFA v.2.0
http://img147.imageshack.us/img147/986/bneanea7zz.jpg

Abgesehen davon, dass p statt z0 der Startzustand sein sollte,
müsste es jetzt richtig sein.

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 17:34
Anonymer User
Richtig, [img]http://mokrates.de/cgi-bin/texstring?L%3D%5C%7Bw%5Cin%5C%7Ba%2Cb%5C%7D%5E*%5Cmid%20%7Cw%7C_b%5Cge%201%5C%7D[/img].
Dann überlegt man sich leicht [img]http://mokrates.de/cgi-bin/texstring?L%5E%2B%5Csubseteq%20L[/img], also
[img]http://mokrates.de/cgi-bin/texstring?L%5E%2B%3DL[/img] und damit [img]http://mokrates.de/cgi-bin/texstring?L%5E*%3DL%5E%2B%5Ccup%5C%7B%5Clambda%5C%7D%3DL%5Ccup%5C%7B%5Clambda%5C%7D[/img],
d.h. man muss nur das leere Wort hinzufügen.

Ich kann mir nicht vorstellen wie der Automat dann aussieht…

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 18:16
georg
Ich kann mir nicht vorstellen wie der Automat dann aussieht…

Wie gesagt: z0 zum Endzustand machen. [img]http://www.fb18.de/gfx/17.gif[/img]

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 18:57
Anonymer User
ach so weil wenn
w=lambda
|w|=0
dann ist |w|b >= 1 ?

Re: F2 Beweis für L^* e Akz(Sigma) aus Folie ? 2005-07-18 20:23
georg
ach so weil wenn
w=lambda
|w|=0
dann ist |w|b >= 1 ?

Nein. Der ursprüngliche Automat, nennen wir ihn A,
akzeptiert die Sprache
[img]http://mokrates.de/cgi-bin/texstring?L%3A%3DL(A)%3D%5C%7Bw%5Cin%5C%7Ba%2Cb%5C%7D%5E*%5Cmid%20%7Cw%7C_b%5Cge%201%5C%7D[/img]
und du wolltest einen Automaten konstruieren, der die
Sprache L* akzeptiert. Das kann man nun entweder mit dem
Verfahren von der Folie machen oder, indem man
lambda-Kanten von den Endzuständen zum Startzustand
zieht. Diese Verfahren funktionieren immer. In diesem
speziellen Fall aber geht es auch auf eine andere
Weise, weil hier [img]http://mokrates.de/cgi-bin/texstring?L%5E%2B%3DL[/img] gilt (das gilt natürlich
nicht für jede Sprache!). Und weil das eben gilt,
muss man für einen Automaten, der L* akzeptiert, den
Automaten A nur soweit abändern, dass der neue Automat
zusätzlich das leere Wort akzeptiert. Natürlich gilt
nicht [img]http://mokrates.de/cgi-bin/texstring?%7C%5Clambda%7C_b%5Cge%201[/img], denn das leere Wort enthält keine
Symbole (und sonst wäre ja auch das leere Wort bereits
in L enthalten und die Änderung wäre nicht nötig). Und
die einzige Änderung, die daher nötig ist, besteht darin,
aus z0 einen Endzustand zu machen (wenn man das leere
Wort (und nur dieses) zur akzeptierten Sprache hinzufügen
will, funktioniert dieses Verfahren übrigens nicht immer,
aber es funktioniert hier, weil keine Kanten in den Zustand
z0 führen).