Ich benenne deine Zustände aus dem NEA mal: q0 (ganz links), q1, q2, q3 (der Endzustand).
Der DEA startet auch in q0. Mit einer 1 bleibt er in q0. Mit einer 0 kommt er in den Zustand {q0q1}. Das entspricht dem zusammengefassten Zustand von q0 und q1 aus dem NEA.
Von {q0q1} kommst du dann mit einer 0 nach {q0q1q2}: q0 und q1 sind von q0 aus erreichbar. q2 geht über q1.
Bei n Zuständen im NEA kannst du so maximal 2^n Zustände im DEA erhalten.
Xyarvius
DEA aufstellen
Meine Frage:
Gegeben ist die Sprache über dem Alphabet . Geben sie einen DEA für L an.
Meine Ideen:
Ok, das ist wie ich finde eine sehr interessante Aufgabe, aber ich bin noch nicht auf die Lösung gekommen.
Ein NEA für die Sprache ist kein Problem, aber egal wie ichs bei dem DEA drehe und wende, entweder will ich es zu einem NEA machen oder der DEA passt nicht zur Sprache. Hättet ihr einen Gedankenanstoß für mich?
Im Anhang eine bildliche Darstellung meiner Hoffnungslosigkeit.
Xyarvius hat dieses Bild (verkleinerte Version) angehängt:
