Kann ich auch erst einen nichtdeterministischen EA erstellen und diesen dann umwandeln?

Question

Ist dieser nichtdeterministische Automat für das Problem in b) korrekt?

A = ({0,1}, {s0,s1,s2}, delta, s0, {s2})

mit delta: 

	0	1
{s0}	{s0,s1}	{s0}
{s1}	{s1,s2}	{s0}
{s2}	{s2}	{s0}

Die Überführung mit Potenzmengenkonstruktion in einen deterministischen EA A2, wie in der Aufgabenstellung verlangt, ist leider dann aber nicht richtig, es kommt ein Zustand zu wenig heraus. Habe ich einen Fehler gemacht?

 

Comments

Ihre Frage ist in der Kategorie "Band I, Kapitel 2" gestellt. Aber auf welche Aufgabe beziehen Sie sich? Können Sie die Frage bitte in die richtige Kategorie verschieben (sie sollte die Form "XXX-XX" haben). Sie müssen dazu einfach auf "Bearbeiten" klicken und die entsprechende Kategorie auswählen; diese ist unterhalb des Titels der Aufgabe in der PDF-Datei angegeben.

Answer 1

Es ist natürlich möglich zuerst einen nichtdeterministischen Automaten zu erstellen und diesen in einen deterministischen umzuwandeln.

Allerdings ist dein Nichtdeterministischer Automat falsch. Beispielsweise gelangt man bei deinem nichtdet. EA bei der Eingabe einer 0 in s0 nicht in einen Endzustand. Dies müsste jedoch der Fall sein.

LG

Lorena (Tutorin)