• Increase font size
  • Default font size
  • Decrease font size

Geister haben die Wahl

Drucken

 Michael Rabin Michael O. Rabin

Ein nichtdeterministischer Automat (NEA) kann als Reaktion auf eine Eingabe, also auf das selbe Terminalsymbol mehrere verschiedene Folgezustände annehmen. Unsere Geister haben also die Wahl nach einem "Hu" ein weiteres "Hu" folgen zu lassen oder in ein "Heul" überzugehen. Unter dieser Voraussetzung ist es möglich, einen Automaten zu - vermuten -, ihn auch in der Folge einfacher zu entwerfen.
Auch NEA's gehören genau wie die deterministischen endlichen Automaten (DEA's) zu den regulären Sprachen.

Satz (Rabin,Scott): Zu jedem nichtdeterministischen endlichen Automaten gibt es einen äquivalenten deterministischen endlichen Automaten.


Applet zur Veranschaulichung eines NEA's zur Geisterschreisimulation

Eine Einbindung in die eigene Seite ist wie folgt möglich:

<iframe scrolling="no"  frameborder=0  width="700"  height="300"  src="http://www.g-ymnasium.de/Java/geister/geistergui.html"></iframe>


[Quelle Geisterbilder: http://tanzgeister.de/sonst3.htm]                

        Aufgabenstellung   |        Lösungsvorschlag  

        Simulation in Python 3.1 

        Javaprogramm

        Prüfprogramm für Sprachzugehörigkeit

 

(c) g-ymnasium.de 2006 - 2013 + Administrator