3. Ist der DEA richtig?

Ist der DEA richtig?

  • K

    Welches Wort hab ich übersehen, das er dennoch akzeptiert?

    Andersherum, es gibt Woerter in der Sprache, die er nicht akzeptiert, aber akzeptieren sollte. Siehe Edit open. Desweiteren hast du dein Alphabet nicht angegeben, aber ich tippe mal auf E = { a, b }.

    0
  • V

    Hm, du hast Recht!

    Dann sollte er nun so passen: http://s14.directupload.net/file/d/3307/k58noitj_jpg.htm

    Er hat zwar immer noch keine 3 Zustände aber das ist ja doch für die Funktion egal, oder? Jetzt erkennt auch bbba

    E = {a,b}

    0
  • B

    Was ist mit dem leeren Wort? Oder einem, das nur aus a's besteht? 0 ist auch durch 3 teilbar.

    0
  • J

    Das wort 'a' wird immer noch niht akzeptiert.

    Überleg dir mal wie knivil auf drei zustände kommt. Vielleicht findest du dann eine zielführende konstruktion, die "offensichtlich" richtig ist? Momentan (und das zuminedst gefühlt seit jahren) bastelst du offensichtlich ad hoc rum und lässt dann von uns verifizieren, ob das stimmt. Um weiterzukommen solltest du a) dringend lernen sowas selber zuverlässig zu überprüfen und b) dir eine systematische konstruktionsmethode zulegen (nein, irgendwie anfangen und nach und nach immer mehr zustände und übergänge hinzufügen, ist keine systematische methode). Sonst machen wir in drei Jahren noch immer dasselbe -- und das wär doch langweilig, oder?

    0
  • V

    Mir wurde gesagt und das sehr oft, dass in diesem Bereich keine "systematische konstruktionsmethode" gibt.

    Ich hab mir auch schon überlegt, über eine Äquivalenzklassenberechnung zu gehen. Anzahl b's durch 3 teilbar, ist ja nix anderes wie modulo 3. Hat aber auch nicht geklappt.

    Für das leere Wort würde ich einfach den Zustand q0 akzeptierend machen. Für das Wort a, aa, aaa, ... würde ich einfach den Zustand q1 noch akzeptierend machen. Wenn dann der Automat nun richtig ist, würde ich einfach noch den Minimierungsalgorithmus für DEAs drüberlaufen lassen und schon ist er minimal und fertig.

    Was meint ihr kann man das so machen?

    0
  • J

    Es stimmt, dass es (wahrscheinlich) keine systematische methode gibt, die immer funktioniert. Aber in vielen Fällen gibt es das eben doch. Und gerade Übungs- und Klausuraufgaben lassen sich oft sehr schematisch bauen.

    Den richtigen ansatz hast du doch gefunden:

    vip@r schrieb:

    Ich hab mir auch schon überlegt, über eine Äquivalenzklassenberechnung zu gehen. Anzahl b's durch 3 teilbar, ist ja nix anderes wie modulo 3. Hat aber auch nicht geklappt.

    Dann probiers nochmal! 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.

    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.

    0
  • V

    Ich glaub ich hab's jetzt! Ich hab zumindestens kein wort das nicht passt!

    Hier der Automat: http://s14.directupload.net/file/d/3307/pmmhvrx5_jpg.htm

    0
  • S

    Jester schrieb:

    Das wort 'a' wird immer noch niht akzeptiert.

    0
  • J

    Versuchs nochmal. Mach die drei zustände hin (einen pro äquivalenzklasse) und geh dann so vor wie ich oben beschrieben habe. Immer wenn du einen vierten zustand hingemalt hast, legst du den stift bei seite, legst die hand flach mit dem handrücken nach oben auf das papier und ballst sie dann ruckartig zur faust. Dann wirfst du den entstehenden papierball in den mülleimer und fängst von vorne an. Viel erfolg! 👍

    0
  • 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
Anmelden zum Antworten