c++.de :: Stimmt dieser Produktautomat?

vip@r Mitglied 19:19:33 10.05.2012 Titel:

Hi Leute!

Gegeben sind diese Sprachen:

§L_1 = \{ w \in \Sigma^{\star}_{\text{Bool}} | \text{w endet auf 01} \}§

§L_2 = \{ w \in \Sigma^{\star}_{\text{Bool}} | \text{w enthält 00 nicht} \}§

Ich soll nun aus diesen gegeben Sprachen einen Automaten konstruieren, der §L = L_1 - L_2§ erkennt.

Ich hab hier ein Bild mit meiner Arbeit. Ich hab nur leider keine Möglichkeit dieses überprüfen zu lassen und würde mich freun, wenn mir jemand von euch sagen könnte, ob das stimmt!

Bild: http://s14.directupload.net/file/d/2886/bcl2958b_jpg.htm

knivil Mitglied 19:39:20 10.05.2012 Titel:

M_1 ist schon falsch: 10101, naja, M_2 ist auch unvollstaendig.

SG1 Mitglied 19:39:58 10.05.2012 Titel:

Also zum einen fehlt Deinem ersten Automaten eine Kante. 10101 endet mit 01, wird aber nicht von Deinem Automaten nicht erkannt.

Zum anderen kenn ich Den Produktautomaten nur für den Schnitt, nicht die Mengendifferenz... Wobei, Moment: §L = L_1 - L_2 = L_1 \cap \overline{L_2}§, richtig? Und das hast Du jetzt beides in einem Schritt gemacht? Dann solltest Du den 2. Automaten erstmal vervollständigen, bevor Du den den Komplementautomaten (und dann den Produktautomaten) bildest.

vip@r Mitglied 20:06:49 10.05.2012 Titel:

Ich hab für den Automaten M_1 erst einen NEA gemacht und den mit der Potenzmengenkonstruktion zu einem DEA gemacht.

q0 -(0)-> q1 -(1)-> q2

q0 hat noch eine 0,1-Eigeschleife und q2 ist akzept. Das ist der NEA.

Ist der NEA schon falsch?

SG1 Mitglied 20:23:38 10.05.2012 Titel:

edit: hier stand mist

So, 2. Versuch ^^

Der NEA ist richtig. Und ich versteh gerade nicht, wofür Du für L_1 überhaupt 'nen DEA brauchst. Die Produktkonstruktion funktioniert doch auch für NEA, IIRC. Nur für L_2 brauchste 'nen DEA.

Und nun der hoffentlich letzte Edit: Ich glaub, ich weiß, was bei Deinem Potenzautomaten schiefgegangen ist. Dir fehlen die Kanten, die vom Endzustand wieder wegführen.

vip@r Mitglied 20:50:10 10.05.2012 Titel:

Was bedeutet IIRC?

Dass man bei einem Produktautomten NEAs und DEAs mischen darf, wusste ich nicht.

Warum braucht man aber zwingend für den M2 einen DEA?

Wenn der NEA von M1 passt was hab ich dann bei der Konstuktion des DEAs mit der PMK falsch gemacht? Ich hab den jetzt noch ein paar mal versucht daraus zu konstruieren, aber ich komm immer wieder auf den gleichen :-(

SG1 Mitglied 20:57:38 10.05.2012 Titel:

vip@r schrieb:

Was bedeutet IIRC?

If I remember correctly. Ist halt schon etwas her, dass ich die Vorlesungen dazu gehört hab

Zitat:

Dass man bei einem Produktautomten NEAs und DEAs mischen darf, wusste ich nicht.

Naja, DEAs sind ja auch NEAs. Und die eigentliche Produktautomatenkonstruktion (die für die Bildung des Schnitts) funktioniert für alle NEAs.

Zitat:

Warum braucht man aber zwingend für den M2 einen DEA?

Weil Du da ja vorher noch das Komplement bilden musst. Und die simple Konstruktion (einfach Endzustände und nicht-Endzustände vertauschen) funktioniert halt nur für vollständige(!) DEAs.

Zitat:

Wenn der NEA von M1 passt was hab ich dann bei der Konstuktion des DEAs mit der PMK falsch gemacht? Ich hab den jetzt noch ein paar mal versucht daraus zu konstruieren, aber ich komm immer wieder auf den gleichen :-(

Siehe mein letztes Edit im vorherigen Post.

vip@r Mitglied 21:21:20 10.05.2012 Titel:

Ich habe gelernt, dass man die Mengendifferenz auch so bilden kann, in dem man einen Produktautomaten bildet und dann die akzept. Zustände markiert. Die im Produktautomaten akzept. Zustände sind dann in meinem Fall die Zustände bei denen nur die Zustände akzept. die in Sprache L2 akzeptieren. Von Sprache L1 darf kein Zustand akzeptieren...

Ich hoffe man kann verstehen was ich hier geschrieben hab.

Edit:

Ich hab hier dann mal die neuen Versionen der beiden Automaten als Bild. Bei der neuen Transition hab ich nur leider das Gewicht der Kante vergessen. Das muss natürlich "0" heißen. Hier das Bild: http://s14.directupload.net/file/d/2886/bqu6s8h5_jpg.htm

SG1 Mitglied 21:32:43 10.05.2012 Titel:

vip@r schrieb:

Ich habe gelernt, dass man die Mengendifferenz auch so bilden kann, in dem man einen Produktautomaten bildet und dann die akzept. Zustände markiert.

Wie gesagt - für mich klingt das wie 2 Schritte in einem. Aber wenn man das richtig macht, ist das möglich.

Zitat:

Die im Produktautomaten akzept. Zustände sind dann in meinem Fall die Zustände bei denen nur die Zustände akzept. die in Sprache L2 akzeptieren. Von Sprache L1 darf kein Zustand akzeptieren...

Ich hoffe man kann verstehen was ich hier geschrieben hab.

Ne, so ganz nicht. Meinst Du nicht eher: "Die akzeptierenden Zustände des Produktautomaten sind die, wo M1 akzeptiert, aber M2 nicht."? Das funktioniert aber immernoch nur dann, wenn Du M2 vorher vervollständigst.

Zu Deinem edit: Ja, die beiden sehen doch gut aus. Jetzt nur noch den Produktautomaten bilden

vip@r Mitglied 21:41:26 10.05.2012 Titel:

Gut :-)

Hier dann mal der Produktautomat: http://s14.directupload.net/file/d/2886/7ep5uxrv_jpg.htm

Die akzept. Zustände hab ich mal zur besseren Übersichtlichkeit rot gezeichnet. Und ja, ich hab das so gemeint: "Die akzeptierenden Zustände des Produktautomaten sind die, wo M1 akzeptiert, aber M2 nicht."

-> Was verstehst du unter M2 vervollständigen?

SG1 Mitglied 21:58:10 10.05.2012 Titel:

vip@r schrieb:

Gut :-)

Hier dann mal der Produktautomat: http://s14.directupload.net/file/d/2886/7ep5uxrv_jpg.htm

Ich seh keinen Fehler

Zitat:

-> Was verstehst du unter M2 vervollständigen?

Das, was Du jetzt schon gemacht hast: Den Zustand DS im 2. Automaten ergänzen. (Vollständiger DEA: Von jedem Zustand geht zu jedem Eingabesymbol genau ein Pfeil weg)

daki Mitglied 22:16:07 10.05.2012 Titel:

der Automat akzeptiert 011

und terminieren tut er auch nicht, wenn 00 gelesen wird kann er sofort in den DS gehen.

vip@r Mitglied 22:17:00 10.05.2012 Titel:

SG1 schrieb:

Ich seh keinen Fehler

Ich nehme mal an, dann passt auch die Methode, Zitat: "Die akzeptierenden Zustände des Produktautomaten sind die, wo M1 akzeptiert, aber M2 nicht."

Danke für deine ausführliche Hilfe! Hast mir sehr weiter geholfen!

SG1 Mitglied 22:36:41 10.05.2012 Titel:

vip@r schrieb:

SG1 schrieb:

Ich seh keinen Fehler

Ich nehme mal an, dann passt auch die Methode, Zitat: "Die akzeptierenden Zustände des Produktautomaten sind die, wo M1 akzeptiert, aber M2 nicht."

Danke für deine ausführliche Hilfe! Hast mir sehr weiter geholfen!

Ja, die Methode passt.

@daki: von welchem Automaten redest Du?

knivil Mitglied 23:36:16 10.05.2012 Titel:

Ich will nur dran erinnern:

vip@r schrieb:

Wie ich dieses Forum liebe!

Arrivi derci.

daki Mitglied 09:54:43 11.05.2012 Titel:

dem da..

http://s14.directupload.net/file/d/2886/7ep5uxrv_jpg.htm

wenn das der Produktautomat von den beiden hier sein soll:

http://s14.directupload.net/file/d/2886/bqu6s8h5_jpg.htm#

edit.: bin mir gerade nicht sicher, evtl. steh ich auch selbst am Schlauch..