Myhill-Konstruktion

Beschreibung

Die MyHill'sche Teilmengenkonstruktion ist eine Vorgehensweise der Theoretischen Informatik, die einen nicht-deterministischen, endlichen Automaten deterministisch macht. Dazu werden aus dem nicht-deterministischen Automaten verschiedene Teilmengen gebildet, die die Grundlage für den deterministischen Automaten bilden.

Die Konstruktion wird angewandt, da deterministische Automaten gegenüber nicht-deterministischen einige Vorteile haben. Sie ist für jeden nicht-deterministischen, endlichen Automaten anwendbar.

Vorgehensweise

Um aus einem nicht-deterministischen endlichen Automaten (NEA) $A_{n}=(S,T,\Delta ,I,F)$ eine deterministischen endlichen Automaten (DEA) $A_{d}=(S',T,\Delta ',I',F')$ zu erzeugen, sind folgende Schritte notwendig:

Zustände

Die Zustände $S'$ des deterministischen Automaten $A_{d}$ bildet die Potenzmenge $S'=2^{S}$. Die Mengenelemente $s_{i}\in S'$ werden zur Vereinfachung der Schreibweise als $s_{0}',s_{1}',\ldots ,s_{n}'$ bezeichnet, behalten jedoch ihre eigentliche Menge aus Zuständen $s\in S$. Es gilt bspw: $s_{1}'=\{s_{1},s_{2}\}$.

Alphabet

Das Alphabet $T$ wird nicht verändert.

Startzustände

Da deterministische Automaten nur einen Startzustand besitzen dürfen, hat die Menge $I'$ nur ein einziges Element: die Menge $I$ aller Startzustände des NEA. Es gilt $I'=\{I\}$.

Endzustände

Die Menge $F'$ enthält alle Zustände aus $S'$, die einen Endzustand aus $F$ beinhalten. Somit gilt: $F'=\{s'\in S'|s'\cap F\neq \emptyset \}$.

Übergänge

Um die Menge der Übergänge $\Delta '$ zu ermitteln, geht man vom Startzustand $s_{n}'\in S'$ aus. Diesem wurden im Schritt "Zustände" verschiedene Elemente $s\in S$ zugeordnet. Man überprüft nun für alle $t\in T$, welche Übergänge im NEA mit $t$ erreichbar sind und erhält eine Menge von Zuständen ${\overline {s_{n}'}}=\{s\in S\}$ mit $s_{n}'t\Rightarrow {\overline {s_{n}'}}$. Diese Menge findet sich als Element in $S'$ wieder, sodass genau ein Folgezustand bestimmt werden kann. Für alle so entstandenen Zustände, die bisher noch nicht behandelt wurden, wird ebenso verfahren, bis keine neuen Zustände mehr entstehen