3. Wieder eine Automate-Konstruktion

Wieder eine Automate-Konstruktion

  • V

    Also so: http://imageshack.us/photo/my-images/97/67131033.jpg/

    0
  • V

    vip@r schrieb:

    Also so: http://imageshack.us/photo/my-images/97/67131033.jpg/

    Richtig.

    (Der läßt sich noch ein wenig optimieren, weil zufällig die Zustände 2 und 3 für beide Symbole jeweils den selben Nachfolgerzustand (den akzeptierenden) haben. Die beiden lassen sich zusammenfassen zu einem Zustand.)

    0
  • V

    Ja genau. Das hab ich grad schon noch gemacht.ich hab jetzt 4 Zustände jeweils mit einer 0,1-Kante verbunden. Der dritte erkennt und der vierte ist der Fehlerzustand mit einer 0,1-Eigenschleife.

    Ich hab jetzt hier gleich noch mal eine eine Sprache L von der ich zwar schon angefangen hab, aber jetzt nicht mehr weiter weiß:

    L = {z aus Σ*Bool | z = u1110110v, mit u, v aus Σ*Bool}

    u und v sind quasi beliebige Wörte aus Σ. Ich hab jetzt mal einen Automaten dastehen, der mir das mittlere Wort vollständig "herausschneidet" und an dessen letzten Zustand noch einen allerletzten akzept. Zustand welcher mir dann alles erkennt was noch kommt. Soweit sollte das schon richtig sein.

    Mein Problem besteht nun darin, dass erste Wort u herauszufiltern und zu entscheiden wann des mittlere "definierte" Wort beginnt...

    0
  • V

    vip@r schrieb:

    Ich hab jetzt hier gleich noch mal eine eine Sprache L von der ich zwar schon angefangen hab, aber jetzt nicht mehr weiter weiß:

    L = {z aus Σ*Bool | z = u1110110v, mit u, v aus Σ*Bool}

    q0: 0->q0  1->q1 //Bisher erkannt: u
q1: 0->q0  1->q2 //Bisher erkannt: u1
q2: 0->q1! 1->q3 //Bisher erkannt: u11
q3: 0->q4  1->   //Bisher erkannt: u111
q4: 0->    1->q5 //Bisher erkannt: u1110
q5: 0->    1->q6 //Bisher erkannt: u11101
q6: 0->    1->   //Bisher erkannt: u111011
q7: 0->q7  1->q7 //Bisher erkannt: u1110110v

    Das Vorwärtsgehen ist ganz leicht.
    Aber das Zurückfallen bei falschem Zeichen ist voll übel.
    Zum Beispiel wird aus u111011 durch Anfügen einer 1 dann u111. Die drei letzen Zeichen waren ja 111, ich darf also bei Fehler nicht bis q0 zurückspringen, sondern muß immer überlegen, bis wohin genau.

    0
  • V

    Also ich weiß ja nicht so genau, aber das ist wahrschenlich eh wieder falsch:

    q0: 0->q0  1->q1 //Bisher erkannt: u
q1: 0->q0  1->q2 //Bisher erkannt: u1
q2: 0->q1! 1->q3 //Bisher erkannt: u11
q3: 0->q4  1->q3 //Bisher erkannt: u111
q4: 0->q4  1->q5 //Bisher erkannt: u1110
q5: 0->q4  1->q6 //Bisher erkannt: u11101
q6: 0->q5  1->q7 //Bisher erkannt: u111011
q7: 0->q7  1->q7 //Bisher erkannt: u1110110v
    0
  • J

    Das Problem ist, dass der Automat ja nicht gesagt kriegt "so, jetzt ist das u fertig, jetzt kommt der festgelegte text aus der mitte". er muß also selbst rausfinden, ob die bisherige Eingabe schonmal das feste Wort aus der Mitte enthalten hat.

    Bau doch erstmal einen nicht-deterministischen Automaten (das ist nicht so schwer) und mach den dann deterministisch.

    0
  • V

    Gut. Ein NEA sollte doch dann so aussehen:

    q0: 0,1->q0 1->q1
q1: 1->q2
q2: 1->q3
q3: 0->q4
q4: 1->q5
q5: 1->q6
q6: 0->q7
q7: 0,1->q7

    Stimmt das so?

    0
  • V

    So, hier dann mal der DEA, der durch Umwandlung vom NEA entstanden ist. Ich hab jetzt einen Zustand mehr als vorher. Vielleicht kann das mal einer von euch überprüfen! Danke!

    http://imageshack.us/photo/my-images/402/47590980.jpg/

    Edit: Die nicht bezeichnete Kante ist eine 0-Kante...

    0
  • J

    Hallo,

    Dein NEA sieht gut aus (mal geraten was anfangs- und endzustände sind). Mit der Umwandlung bin ich noch nicht ganz einverstanden:

    - von q_4 muß es noch einen Pfeil zu q_0 geben, wenn man ne 0 eingibt
    - der 1-Pfeil von q_6 muß imo zu q_2 gehen, an der stelle hat man ja schon zwei 1en hintereinander gesehen

    - q_7 und q_8 sind quasi derselbe zustand

    0
  • V

    Ich hab dann mal die Potenzmengenkonstruktion neu gemacht und bin dann auf folgenden DEA gekommen: http://imageshack.us/photo/my-images/6/32334606.jpg/

    Warum aber nun die 1er-Kante von q6 aus nach q2 (und nicht nach q3 wie in meinem neuen DEA) gehen soll, verstehe ich nicht.

    Woran du siehst, dass q7 und q8 eigenlich gleiche Zustände sind, würde mich auch sehr interessieren!

    Edit: Ich zähl die Mengenzustände genauso durch wie die Zustände des NEAs. Verstehst du was ich meine?

    0
Anmelden zum Antworten