Unterschied zwischen Nichtdeterministischen und deterministischen endlichen Automaten?

... komplette Frage anzeigen

2 Antworten

Ein nicht deterministischer Automat kann bei gleicher Eingabe unterschiedliche (zufällige) Zustände annehmen. Ein deterministischer Automat wird auf die gleiche Eingabe immer gleich reagieren, also immer den gleichen Zustand annehmen. Ein ganz einfaches Beispiel wäre: Du hast eine Ampel, die auf die eingaben : {rot, gelb, grün} auf die Weise regiert, dass immer genau ein Lampe leuchtet, die der Farbe der Eingabe entspricht. Man könnte zum Beispiel einen nicht deterministischen Automaten erfinden, der die Eingaben {r, g} versteht und bei "r" zwar immer Rot leuchten lässt, aber bei der Eingabe "g" entweder Gelb oder Grün oder beides.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von iParadox15
16.12.2015, 22:53

Das heißt in deinem Beispiel mit der Ampel in einem NEA gehen von der Eingabe "g" zwei Pfeile zu zwei verschiedenen Zuständen, oder? Also Gelb oder Grün.

Kann man einen DEA zu einem NEA umformen, indem man einfach mehr als eine Eingabe zur Verfügung hat, um vom Startzustand (q0) zum Zustand q1 überzugehen? Dann müsste man aber einen weiteren Zustand einbauen, oder?

0

Aho Ullmann nochmal lesen ("Ritter" Buch)

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?