Nichtdeterministische endliche Automaten NEAs(nicht im BP)

Nichtdeterministische Automaten kommen im Bildungsplan nicht vor und werden hier nur der Voll­stä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 „Zweifels­fällen“ darf ein NEA „richtig raten“¹⁴ . 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 konstruie­ren, als einen DEA. Außerdem kann (etwas überraschend) jeder NEA in einen DEA umgewandelt werden, der genau die gleiche Sprache erkennt. Weil diese Umwandlung¹⁵ 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äch­tiger 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.

¹⁴ 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.

¹⁵ 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