Potenzmengenkonstruktion

Schon die Überschrift verspricht eine komplizierte, mühsame und langwierige Prozedur - und so ist es leider auch.

Aber das Zentralabitur will die Informatik-Schüler in NRW trotzdem damit beglücken...

Wozu?

Mithilfe der Potenzmengenkonstruktion kann man einen Deterministischen Endlicher Automat (DEA)in einen Nicht-deterministischen endlichen Automaten (NEA) überführen.

Grundidee

Die Grundidee ist reichlich abstrakt und hier - mit Absicht - sehr kurz gehalten. Man kann das sowieso erst verstehen, wenn man mal ein Beispiel durchexerziert hat...

Der NEA kann sich bei gleicher Zeichenfolge "zeitgleich" in mehreren verschiedenen Zuständen befinden - je nachdem, welchen "Weg" man bei einem nicht-deterministischen Übergang gewählt hat.

Ein Zustand des DEA fasst all diejenigen Zustände des NEA zusammen, in denen sich der NEA zu einem bestimmten Zeitpunkt befinden könnte.

Beispiel

Youtube-Tutorial

Wer Youtube-Erklärungen mag, ist hier richtig: NEA zu DEA Transformation (Youtube).
Man muss aber mindestens 17 Minuten Zeit haben, um die beiden Teile des Tutorials anzusehen! Und um es richtig zu verstehen, muss man vermutlich ab und zu nochmal zurückspulen...

Konventionell

Das folgende Beispiel kommt von Potenzmengenkonstruktion Wikipedia und ist dort unter der CC BY-SA 3.0 veröffentlicht.