Potenzmengenkonstruktion
Mit der Potenzmengenkonstruktion kann ein nicht-deterministischer Automat in einen deterministischen Automaten umgewandelt werden. Dies ist vor allem dann nützlich, wenn ein es, um zu einem Zustand zu gelangen nur eine Möglichkeit und nicht mehrere gegen darf.
Beispiel
Aufschreiben der Zustände
Für das Verfahren werden zwei Tabellen aufgestellt: In einer ersten Tabelle werden alle möglichen Zustände des NEA notiert.
| Zustand | a | b | c |
|---|---|---|---|
| Q_{0} | Q_{12} | \varnothing | \varnothing |
| Q_{1} | \varnothing | Q_{1} | \varnothing |
| Q_{2} | \varnothing | \varnothing | Q_{2} |
Aufstellen der Trafo-Tabelle
Danach wird eine Trafo-Tabelle erstellt, welche dann auch als Endtabelle für den DEA gilt. Hier wird der erste Zustand genau so abgeschrieben, wie in der NEA Tabelle. Findet sich dann aber ein Zustand wie Q_{12}, wird dieser als ein neuer Zustand deklariert. So wird dies für alle weiteren Zustände durchgeführt, bis alle Zustände einmal vorhanden sind.
Es ergibt sich nun folgende Tabelle:
| Zustand | a | b | c |
|---|---|---|---|
| Q_{0} | Q_{12} | \varnothing | \varnothing |
| Q_{12} | \varnothing | Q_{1} | Q_{2} |
| Q_{1} | \varnothing | Q_{1} | \varnothing |
| Q_{2} | \varnothing | \varnothing | Q_{2} |
Zeichnen des DEA
Dann wird aus dieser Tabelle der DEA gezeichnet, mit diesen Zuständen. Der Fertige Automat sieht so aus:
