Unterschied zwischen Nichtdeterministischen und deterministischen endlichen Automaten?
Habe zwei Fragen:
Was ist der Unterschied zwischen einem NEA und einem DEA? Wie "forme" ich einen DEA zu einem NEA um und umgekehrt?
Habe gegoogelt, aber die Erklärungen kapier ich irgendwie nicht..
Danke!
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.
Sicher, dass DEA -> NEA gefragt ist? Strenggenommen ist ein DEA nämlich schon ein NEA, jedenfalls nach Definition. NEA -> DEA ist eigentlich so die Standard-Frage, die mittels Potenzmengenkonstrukrion gelöst wird.
Und wie funktioniert das umformen von NEA zu DEA? Bin da jetzt nicht so gut in dem Thema...
Also ich habe gelernt, wenn man durch mehrere Eingaben (min. 2) von den Startzustand in einen anderen Zustand übergehen kann, ist das ein NEA.
Herrje, ich glaube das bekommt man hier so knapp nicht hin. Der Weg zu Fuß sieht meist vor, dass man aus einem gegebenen Automaten einen regulären Ausdruck über das Eingabealphabet baut und dann in einen DEA transformiert, wobei die Lösung zunächst EINE Lösung des Problems darstellt, denn häufig wird ja der Automat mit minimalen Zuständen gesucht.
Danke für deine Bemühungen und du hast mir trotzdem gut geholfen! :)
Aho Ullmann nochmal lesen ("Ritter" Buch)
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?