Potenzmengenkonstruktion

Die Idee dabei ist dass der DEA in seinem Zustand die Zustände kodiert denen sich der NEA befinden "könnte". Jeder des DEA entspricht somit einer Teilmenge der des NEA. Wenn es im NEA aus <math>z_0</math> mit Eingabe von "a" eine Transition Zustand <math>z_1</math> und in <math>z_2</math> gibt gibt im DEA eine von Zustand <math>\{z_0\}</math> in Zustand <math>\{z_1 z_2\}</math>. Hat der NEA eine Transition für dieselbe Eingabe von <math>z_3</math> nach so hat der DEA auch eine von z_3\}</math> nach <math>\{z_1 z_2 z_4\}</math>. Ein größeres wird ergänzt.

Formal gilt dabei:

Sei A:=(Q <math>\Sigma</math> <math>\delta</math> s F) NEA.

<math>\tilde Q=2^Q</math>

<math>\tilde\delta:\tilde Q \times \Sigma \rightarrow \tilde wobei <math>\tilde \delta (\tilde q a)=\hat q(\tilde a)</math> für <math>a \in \Sigma</math>.

<math>\tilde s := E(s)</math> (<math>\epsilon</math>-Abschluss)

<math>\tilde F := \left\{\tilde q \in Q | \tilde q \cap F \neq \right\}</math>

<math>\tilde A = \left\{\tilde Q \Sigma \delta \tilde d \tilde F \right\}</math> ist zu dem NEA A äquivalente DEA.

In der Regel sind viele der des neuen Automaten nicht erreichbar und können einem weiteren Vereinfachungsschritt weggelassen werden. In der würde man eine Variante der Konstruktion benutzen der gleich nur der erreichbare Teil des erzeugt wird. Es gibt Beispiele die zeigen sich das exponentielle Anwachsen der Zustandsanzahl nicht vermeiden läßt.

Bücher zum Thema Potenzmengenkonstruktion

Dieser Artikel von Wikipedia unterliegt der GNU FDL.