Nichtdeterministische endliche Automaten NEAs(nicht im BP)
Nichtdeterministische Automaten kommen im Bildungsplan nicht vor und werden hier nur der Vollständigkeit halber erwähnt.
In einem NEA darf es auch Transitionen geben, die der Automat durchlaufen kann, ohne dabei Eingabezeichen zu „verbrauchen“. Außerdem sind mehrdeutige Übergänge (von einem Zustand bei gleicher Eingabe zu unterschiedlichen Zielen) erlaubt. Bei all diesen „Zweifelsfällen“ darf ein NEA „richtig raten“14 . Immer richtig raten geht natürlich nicht, so dass NEAs nicht implementiert werden. Sie leisten aber sehr gute Dienste als Zwischenergebnis: Oft ist es nämlich einfacher, einen NEA zu konstruieren, als einen DEA. Außerdem kann (etwas überraschend) jeder NEA in einen DEA umgewandelt werden, der genau die gleiche Sprache erkennt. Weil diese Umwandlung15 auch wieder automatisch erfolgen kann, genügt es in der Regel, für die Erkennung einen NEA zu bauen. DEAs und NEAs sind also gleich mächtig: DEAs sind natürlich schon laut Definition nicht mächtiger als NEAs – und weil jeder NEA sich in einen äquivalenten DEA umwandeln lässt, sind auch NEAs nicht mächtiger als DEAs. Sie können also exakt die gleichen Sprachen erkennen: Die sogenannten reguläre Sprachen. Für die Beschreibung regulärer Sprachen gibt es reguläre Grammatiken als eher theoretisch orientiertes, und die schon erwähnten regulären Ausdrücke (ab Seite 17) als äußerst praktisches Beschreibungsmittel.
14 In einer äquivalenten Formulierung „rät“ der Automat nicht, sondern befindet sich in mehreren Zuständen gleichzeitig. Auf dieser Idee basiert auch die sogenannte Potenzmengenkonstruktion.
15 Diese Umwandlung wird als Potenzmengenkonstruktion bezeichnet. NEAs und die Potenzmengenkonstruktion eignen sich als 1-2 GFS-Themen für starke Schüler.
Hintergrundinformationen: Herunterladen [odt][669 KB]
Weiter zu Kellerautomaten