DEA angeben?



  • Hi Leute!

    Mir ist die folgende Sprache gegeben:

    L={aibjcki,j,kN0}L = \{ a^i b^j c^k | i,j,k \in \mathbb N_0 \}

    Der ε-Nea ist ja recht einfach zu bewerkstelligen. Einfach 3 Zustände mit jeweils einer Eigenschleife mit a,b,c und zwischen den 3 Übergängen jeweils eine ε-Transition und der letzte Zustand ist akzeptierend.

    Aber der DEA für diese Sprache stellt mich vor größere Probleme. Natürlich hab ich hier auch wieder 3 Zustände; aber die Übergänge sind das Problem! Wenn ich vom ersten Zustand zum zweiten mit einem b weitergehe, dann fordere ich ja mindestens ein b. Laut Sprache soll aber weder a, b noch c akzeptiert werden können, weil die Potenzen aus N0\mathbb N_0 kommen.



  • Dann wandele den NEA eben in einen DEA um.
    http://de.wikipedia.org/wiki/Potenzmengenkonstruktion

    Seit wievielen Monaten lernst Du eigentlich schon diesen Kram?



  • vip@r schrieb:

    zwischen den 3 Übergängen jeweils eine ε-Transition

    Wozu denn die ε-Übergänge? Du weißt doch ganz genau bei welcher Eingabe du in den nächsten Zustand gehen musst.



  • Dass ich den ε-NEA in einen DEA umwandle hab ich auch schon dran gedacht. Das Problem ist dann aber, weil ich nicht weiß, wie ich mit den ε-Transitionen umgehen soll...
    Wie verhalten sich diese Transitionen bei einer PMK?

    @Tobiking: Es heißt ja, ich soll einen ε-NEA bauen! Dann werd ich ja wohl auch ε-Transitionen brauchen, oder?



  • Wenn du beides angeben musst, dann kannst du die Übergänge natürlich erstmal nutzen. Ich hatte gedacht du versuchst jetzt den DEA mit Umweg zu konstruieren. Das ginge nämlich einfacher wenn du dir einfach überlegst wann die Übergänge passieren und direkt den DEA bastelst.

    Du kannst aber auch trotzdem direkt den DEA bauen und den zusätzlich als NEA angeben. Dich zwingt ja bei NEA keiner den Nichtdeterminismus auch zu verwenden. 😉


Log in to reply