3. Ist der DEA richtig?

Ist der DEA richtig?

  • V

    KAnn man diese Äquivalenzklasse nicht irgendwie berechnen? Einen Automaten für Modulo3 auf binär Ebene zu bauene ist überhaupt kein Problem. Das kann man berechnen; geht das hier nicht?

    Ich komm einfach nicht drauf

    Wort besitzen modulo 3 entweder 0,1 oder 2 'b's
    Also legst du einen zustand pro äquivalenzklasse und und nun überlegst du dir, welche zustände startzustände sind, welche endzustände und was bei jedem davon bei eingabe eines zeichens passiert.

    Kannst du nochmal genauer drauf eingehen? Was ich nicht verstehe, ist, warum 2 durch 3 teilbar sein soll! Wenn ich hier also nun drei Äquivalenzklassen habe, brauche ich auch 3 Zustände, soweit so gut.

    Meiner Ansicht nach, muss gleich der ersten Zustand akzeptierend sein, wenn ein a schon akzeptierend sein soll, da ja 0 durch 3 teilbar ist!

    Und hier nun vielleicht endlich die Lösung: http://s7.directupload.net/file/d/3308/i3nufc8m_jpg.htm

    Ich hab dann auch gleich noch versucht eine reguläre Grammatik angegeben: G={V={S,A,B},Σ={a,b},P={S→ϵ,S→aS∣bA,A→aA∣bB,B→aB∣bS},S}G=\{V=\{S,A,B\}, \Sigma=\{a,b\}, P=\{S\to\epsilon, S\to aS|bA, A\to aA|bB, B\to aB|bS\}, S\}

    Und hier noch der DEA für die Anzahl a's durch 3 teilbar: http://s1.directupload.net/file/d/3308/58buwwnq_jpg.htm

    0
  • K

    warum 2 durch 3 teilbar sein

    Steht nirgends.

    Und hier nun vielleicht endlich die Lösung: http://s7.directupload.net/file/d/3308/i3nufc8m_jpg.htm

    Ja endlich, wo war das Problem?

    Und hier noch der DEA für die Anzahl a's durch 3 teilbar: http://s1.directupload.net/file/d/3308/58buwwnq_jpg.htm

    War bestimmt ein riesen Problem, a's und b's zu vertauschen ...

    0
  • V

    Jester schrieb:

    Und danach bauste den automaten, der akzeptiert genau dann wenn anzahl der a durch 3 teilbar und anzahl der b durch 2 teilbar. -- auch wieder mit erst überlegen, dann bauen.

    Hier dieser Automat: http://s1.directupload.net/file/d/3308/ow3pqwni_jpg.htm

    Richtig?

    Edit: Mir fällt gerade auf, dass ich hier jetzt Anzahl der b's durch 3 teilbar und Anzahl der a's 2 teilbar gemacht hab; aber das tut der Übung ja keinen Abbruch!

    0
  • J

    Nein, der ist offensichtlich falsch. Was passiert denn, wenn das Wort mit b beginnt?
    Außerdem ist der Automat mit 6 Zuständen realisierbar.

    Das sieht schon wieder so aus wie drauflos geschrieben? Überleg dir doch jetzt noch mal, wie die Äquivalenzklassen für das Problem aussehen! Wie komme ich auf 6 Zustände?

    0
  • V

    Naja, die Äquivalenzklassen, sind wohl die aus b's durch 3 teilbar und a's durch 2 teilbar.

    Ich hab mir erst einen Automat für a durch 2 und dann den Automat für b durch 3 und dann mit PMK und Schnittmenge den neuen Automaten gebaut. Kann man das nicht so machen?

    Edit: Ich hab übrigens nur die Transition b von q0 nach q4 vergessen hinzumalen. Und wer sagt nun, dass dieser Automat falsch ist? Er ist doch nur noch nicht Minimal, oder?

    0
  • B

    vip@r schrieb:

    Ich hab mir erst einen Automat für a durch 2 und dann den Automat für b durch 3 und dann mit PMK und Schnittmenge den neuen Automaten gebaut. Kann man das nicht so machen?

    Keine Ahnung, ob man das kann. Naheliegender wäre der Produktautomat.

    0
  • V

    Aaaahhhh, ich meinte ja die Produktautomatenkonstruktion. Ich hab mich nur verschrieben. Dieser Automat ist mit der Produktautomatenkonstruktion entstanden...

    Ich müsste den wahrscheinlich nun nur minimieren und schon bekäme ich den Automaten den ihr auch habt...

    0
  • B

    Wieso hat dein Automat dann 9 Zustände? 2 mal 3 ist bei mir 6.

    0
  • V

    Hier der Automat für "Anzahl a durch 2 teilbar und Anzahl b durch 3 teilbar": http://s14.directupload.net/file/d/3308/96f38xs9_jpg.htm

    Er hat nun 6 Zustände und ich hab einige Wörter ausprobiert, die alle gepasst haben. Könnt ihr nochmal überprüfen?

    0
  • M

    Du bildest das Produkt aus einem Automaten mit 2 und einem Automaten mit 3 Zuständen. Was hälst du davon, die Zustände in einer 2x3-Matrix aufzuzeichnen und die Zustände mit zwei Zahlen statt nur einer zu indizieren? Dann hätten die Indizes einen Sinn und es wäre deutlich übersichtlicher.

    0
  • V

    Soll ich für den Automaten oben eine Tabelle schreiben, welcher Zustand mit welchem Zeichen wo hingeht? Meinst du das?

    0
  • M

    Nein, du sollst die Zustände im Bild sinnvoll anordnen. Bei dir gehen die Kanten kreuz und quer durch den Graphen und man hat keine Ahnung, was genau ein Zustand denn aussagen soll. Vergleiche das mal mit dem hier:
    http://s14.directupload.net/file/d/3308/ho493es3_png.htm
    Ist dieser Automat korrekt? Das kann man beim ersten Hinschauen entscheiden.

    0
  • V

    Wenn ich meinen Automaten nun so in der Art und Weise entzerre, dann komm ich auf den gleichen Automaten die da gezeigt wird. Ich gehe also davon aus, dass mein Automat richtig ist!

    Vielen Dank!

    0
Anmelden zum Antworten