Hi Folks

Ich habe da ein Verständnisproblem mit der Musterlösung 4 (F2):

http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS04/F2/sec/F2loes04.pdf.gz

Und zwar wird in der zweiten Aufgabe ein Lamdafreier Automat erreicht, der dann in einen Potenzautomaten umgewandelt wird.

Wenn ich aber nach meiner Methode vorgehe, bekomme oich eine andere Lösung:

Meine Matrix:

a b

{p} {p,q} {q}
{p,q} {p,q} {q}
{q} {q} 0
0 0 0

Wenn ich diese Übergangsmatrix als Graphen darstelle, sieht dieser ganz anders aus als in der Musterlösung. Der Übergang von {p,q} ist dort a und zurück b. Aber es müßte doch genau anders herum sein, oder? Habe ich was falsch gemacht oder hat sich ein Fehler in der Musterlösung eingeschlichen. (Beispiel-Produktautomat im Skript kann ich mit meiner Methode 100%ig nachvollziehen).


Ich habe auch noch eine Frage. Ich komme einfach beim lernen für die F-Klausur an einer Stelle nicht weiter:

Produktautomaten

Kann mir jemand mal für doofe kurz erklären, wie man aus zwei Automaten einen Produktautomaten konstruiert.

Dankeschön und einen frohen Ferienanfang für alle :-)

Wenn ich aber nach meiner Methode vorgehe, bekomme oich eine andere Lösung:

Kann gut sein, dass ich nicht mehr ganz zurechnungsfähig bin zu so später Stunde, aber wie geht denn deine Methode? Wenn du das nicht aufschreibst kann man schwer was dazu sagen [img]http://www.fb18.de/gfx/25.gif[/img]

Die Musterlösung stimmt übrigens!

Und noch etwas allgemeines: Es steht dir natürlich frei dir eine Methode zu überlegen (hier bspw. um einen DFA zu konstruieren, der äquivalent zu einem NFA ist), aber wenn du dies tust, dann musst du ihre Korrektheit beweisen!! Nur weil es (zufällig?) bei einem Automaten (z.B. dem Beispiel im Skript) klappt, heisst das nämlich noch lange nicht, dass es immer klappen muss! – Bei dem Potenzautomaten im Skript weiss man hingegen, dass diese Konstruktion immer klappt - das ist ja gerade das schöne an der Mathematik [img]http://www.fb18.de/gfx/25.gif[/img]

Produktautomaten

Ein Produktautomat C zu zwei vDFAs A und B akzeptiert genau die Sprache L(C) = L(A) geschnitten L(B), also gerade jene Wörter, die sowohl A als auch B akzeptieren.

Dies erklärt zunächst warum das Alphabet von C gerade der Schnitt der Alphabete von A und B ist (liest A nämlich bspw. ein Symbol, das B gar nicht lesen kann, dann wird dieses Wort ja ganz bestimmt nicht von B akzeptiert, also auch nicht von C. Anders: Die Worte, die C akzeptiert, müssen sowohl von A als auch von B akzeptiert, also insb. auch gelesen, werden).

Die Idee bei der Zustandsübergangsfunktion (die dann auch die Wahl der Zustandsmenge, des Startzustandes und der Endzustände erklärt) ist, dass C im Prinzip beide Automaten Schritt für Schritt gleichzeitig simuliert. C merkt sich in seinem Zustand in welchem Zustand A und in welchem B ist. Ist C also in einem Zustand (z,z'), so heisst dies, dass A im Zustand z und B im Zustand z' ist. Liest C nun ein Symbol a, dann wird geguckt wo A (der sich im Zustand z befindet) beim Lesen eines a hingelangt (bspw. nach u) und wo B (ist im Zustand z') beim Lesen eines a hingelangt (bspw. nach u'), dann gelangt C beim Lesen eines a von (z,z') nach (u,u'). (Dass es immer einen Folgezustand gibt, liegt daran, dass A und B vollständige Automaten sind!) [Nachtrag: Und daran, dass man sich nur die Eingabesymbole ansieht, die sowohl von A als auch von B gelesen werden können, siehe obige Definition des Eingabealphabets von C - ansonsten könnte es nämlich sein, dass man nur für das erste (respektive zweite) Element des Tupels einen Nachfolgezustand hat und nicht weiss, was mit dem anderem Element passieren soll.]

Wenn A nun ein Wort w akzeptiert, dann gelangt er von seinem Startzustand z_0 in einen seiner Endzustände z_e. Akzeptiert B auch das Wort w, so gelangt er von seinem Startzustand z'_0 in einen seiner Endzustände z'_e. C soll dann also von (z_0, z'_0) in (z_e,z'_e) landen. – Und damit genau dies klappt definiert man sich nun die Zustandsmenge, den Startzustand und die Endzustandsmenge von C wie folgt:

Die Zustandsmenge definiert man als das Kreuzprodukt der Zustandsmengen von A und B, d.h. ein Zustand von C ist ein Tupel (z,z'), wobei z ein Zustand von A und z' ein Zustand von B ist. Der Startzustand ist gerade das Tupel mit (z_0,z'_0), wobei z_0 Startzustand von A und z'_0 Startzustand von B ist.
Sinn: A und B fangen beim Lesen eines Wortes natürlich beide in ihren Startzuständen an.
Endzustandsmenge setzt sich aus den Tupeln (z_e,z'_e) zusammen, wobei z_e Endzustand aus A ist und z'_e einer aus B (beachte: A und B können mehrere Endzustände haben, haben bspw. beide zwei Endzustände, so hat C vier!!). Sinn: Wenn C ein Wort akzeptiert, das A und B beide akzeptieren, müssen beide in einem Endzustand landen.


Mit dieser Konstruktion hat man nun erreicht was man erreichen wollte, denn wenn C ein Wort akzeptiert, so gelangt er von seinem Startzustand (z_0,z'_0) in einen seiner Endzustände (z_e, z'_e). Betrachtet man bei der Rechnung von C nur das erste Element des Tupels, so hat man eine Erfolgsrechnung für A, entsprechend für das zweite Element des Tupels und den Automaten B, d.h. wenn C ein Wort w akzeptiert, so akzeptieren auch A und B dieses Wort.

Andersherum akzeptiert A ein Wort, dass auch B akzeptiert, so gibt es Erfolgsrechnungen in A vom Startzustand z_0 in einen Endzustand z_e und in B vom Startzustand z'_0 in einen Endzustand z'_e. Diese Rechnung kann C wieder nachvollziehen, was sich aus der Konstruktion obiger Übergangsfunktion von C ergibt, d.h. auch C akzeptiert das Wort.

Hoff' es hilft [img]http://www.fb18.de/gfx/22.gif[/img]

Cheers,
Frank

Danke erstmal.

Das hat geholfen.
Noch mal zu Poptenzautomaten (PA) und meiner Methode (die glaub ich nicht viel anders ist als der Mathematische Weg):

Ich zeichne mir den Automaten auf, aus dem der PA entstehen soll. Dann schreibe ich ein Matrixgerüst hin (Spaltenbeschriftung von links nach rechts: Ausgangszustand; Eingabesymbole in einer Reihenfolge). Bei der entsprechenden Aufgabe also

Zustand——a——-b

Dann beginne ich mit dem ersten Startzustand und schaue, in welche Zustände man bei der Eingabe der Symbole gelangen kann:

Zustand——a——-b

{p}——–{p,q}—-{q}

Dann gehe ich alle Zustände durch, auch die neu hinzugekommenen. Hier bekomme ich schließlich die Matrix

Zustand——a——-b

{p}——–{p,q}—-{q}
{p,q}——{p,q}—-{q}
{q}——–{p,q}—–0
0———–0——-0

(Die Bindestriche stehen für Leerzeichen und die 0 für die leere Menge).

Wenn ich aus dieser Übergangsmatrix einen Automaten zeichne, komme ich auf ein anderes Ergebnis als in der Musterlösung:

Von {p,q} nach {q} eben als Übergang ein b und von {q} nach {p,q} eben ein a

und nicht umgekehrt wie in der Mustelösung.

Wo ist da der Fehler?

Danke nochmal

Dein Verfahren ist genau richtig. (Mit der Ausnahme, dass du anderes als in der mathematischen Definition nur die initiale Zusammenhangskomponente erhaelst! Es so zu machen (indem man vom Startzustand ausgeht und dann Schritt-fuer-Schritt die Zusammenhangskomponente bestimmt) steht auch im Skript (nur eine Tabelle wie bei dir wird nicht extra erwaehnt) nach der Definition des Potenzautomaten (mein ich zumindest dort mal gelesen zu haben).)

Allerdings stimmt dein Ergebnis genau mit meiner Musterloesung ueberein.
Evtl. wurde die aber nochmal geaendert und ein kleiner Fehler hat sich dann dort eingeschlichen. Ich gucke mal kurz…

Edit: Hab gerade die Musterloesung nochmal gedownloaded und mir angeguckt. Stimmt doch mit deiner Loesung ueberein?

Du willst mich bloss ein wenig aergern, gell [img]http://www.fb18.de/gfx/28.gif[/img]

Cheers,
Frank

Scheiße, mein Fehler. Ich hab die Musterlösung nämlich abgezeichnet und dabei die beiden Pfeile vertauscht.

Sorry

aber ganz viel Dank

wollte dich nicht aergern :-)