Potenzmengenkonstruktion

Konstruktion

Konstruiere einen äquivalenten deterministischen Automaten ${\displaystyle {\mathcal {D}}=(Q',\Sigma ,\delta ',q_{0}',F')}$ folgendermaßen:

1. Starte mit leeren Zustandsmengen ${\displaystyle Q\!\,'}$ und ${\displaystyle F\!\,'}$.
2. Wähle den Startzustand ${\displaystyle q_{0}'=E(S)}$ von ${\displaystyle {\mathcal {D}}}$. Füge ${\displaystyle q_{0}'}$ zur Menge der Zustände ${\displaystyle Q'}$ hinzu.
3. Für alle Zustände ${\displaystyle q\!\,'}$, die bereits in ${\displaystyle Q\!\,'}$ enthalten sind:
   • Für jedes Eingabezeichen ${\displaystyle s\in \Sigma }$:
     • Konstruiere einen Folgezustand ${\displaystyle q''\!\,}$ als Menge aller Zustände, die ${\displaystyle {\mathcal {N}}}$ ausgehend von einem Zustand aus ${\displaystyle q'\!\,}$ unter Eingabe von ${\displaystyle s\!\,}$ erreichen kann. Also ${\displaystyle q'':=\bigcup \{E(\delta (r,s))|r\in q'\}\!\,}$.
     • Füge den Zustand ${\displaystyle q\!\,''}$ zu ${\displaystyle Q\!\,'}$ hinzu, falls er noch nicht in der Menge der Zustände von ${\displaystyle {\mathcal {D}}}$ enthalten ist.
     • Ergänze die Übergangsfunktion ${\displaystyle \delta \!\,'}$ um den Übergang ${\displaystyle \delta \!\,'(q',s)=q''}$.
4. Wiederhole Schritt 3. so lange, bis sich ${\displaystyle Q\!\,'}$ und ${\displaystyle \delta \!\,'}$ nicht mehr ändern.
5. Wähle die Menge der Finalzustände ${\displaystyle F\!\,'}$ von ${\displaystyle {\mathcal {D}}}$ als diejenige Teilmenge von ${\displaystyle Q\!\,'}$, deren Zustände einen Finalzustand aus ${\displaystyle F\!\,}$ enthalten.

Formales

Sei ${\displaystyle {\mathcal {N}}=\left(Q,\Sigma ,\delta ,S,F\right)}$ ein nichtdeterministischer endlicher Automat mit der Zustandsmenge ${\displaystyle Q\!\,}$, dem Eingabealphabet ${\displaystyle \Sigma \!\,}$, der Übergangsfunktion ${\displaystyle \delta \colon Q\times (\Sigma \,\cup \{\epsilon \})\to {\mathcal {P}}(Q)\!\,}$, dem Startzuständen ${\displaystyle S\!\,}$ und der Menge der Finalzustände ${\displaystyle F\!\,}$.

Der ${\displaystyle \epsilon }$-Abschluss ${\displaystyle E(q)}$ (manchmal auch die ${\displaystyle \epsilon \!\,}$-Hülle) eines Zustands ${\displaystyle q}$ unter ${\displaystyle \delta \!\,,}$ ist definiert als

${\displaystyle E:Q\rightarrow {\mathcal {P}}(Q)}$, so dass ${\displaystyle \forall q\in Q:q\in E(q)}$ und ${\displaystyle r\in E(q)\Leftrightarrow \exists p\in E(q):r\in \delta (p,\epsilon )}$.

Der ${\displaystyle \epsilon }$-Abschluss ${\displaystyle E(Q)}$ einer Menge von Zuständen ${\displaystyle Q}$ ergibt sich dann als ${\displaystyle E(Q)=\bigcup \{E(q)|q\in Q\}}$.
Der zu ${\displaystyle {\mathcal {N}}}$ äquivalente Potenzautomat ${\displaystyle {\mathcal {P}}({\mathcal {N}})=\left(P(Q),\Sigma ,{\tilde {\delta }},s',{\tilde {F}}\right)}$ ergibt sich wie folgt:

${\displaystyle s'\!\,=E(S)}$, der ${\displaystyle \!\,\epsilon }$-Abschluss von ${\displaystyle S\!\,}$ unter ${\displaystyle \delta \!\,,}$

${\displaystyle {\tilde {\delta }}:{\mathcal {P}}(Q)\times \Sigma \to {\mathcal {P}}(Q)}$, mit ${\displaystyle {\tilde {\delta }}(q',a)=\bigcup \{E(\delta (p,a))|p\in q'\},}$

${\displaystyle {\tilde {F}}={\Big \{}q'\in P(Q)|q'\cap F\neq \emptyset {\Big \}}.}$

Dieser Potenzautomat ist bereits ein zu ${\displaystyle {\mathcal {N}}}$ äquivalenter DEA aber immer von exponentieller Größe. Durch das Eliminieren von Zuständen die vom Startzustand nicht erreicht werden können ergibt sich der in unserer Konstruktion beschriebene äquivalente DEA ${\displaystyle {\mathcal {D}}=\left(Q',\Sigma ,\delta ',s',F'\right)}$ mit:

${\displaystyle Q'\subseteq {\mathcal {P}}(Q)}$, so dass ${\displaystyle Q'}$ die kleinste Menge ist mit ${\displaystyle s'\in Q'}$ und ${\displaystyle \forall q'\in Q',\forall a\in \Sigma$ :{\tilde {\delta }}(q',a)\in Q',}

${\displaystyle \delta '\colon Q'\times \Sigma \to Q',\delta '={\tilde {\delta }}\mid _{Q'\times \Sigma },}$

${\displaystyle F'={\Big \{}q'\in Q'|q'\cap F\neq \emptyset {\Big \}}.}$

Automat zum regulären Ausdruck (a|b)*aba

Gegeben sei der nichtdeterministische Automat ${\displaystyle {\mathcal {NA}}={\Big (}\{s_{0},s_{1},s_{2},s_{3}\},\Sigma ,\delta ,s_{0},\{s_{3}\}{\Big )}}$ über dem Alphabet ${\displaystyle \Sigma \!\,=\{a,b\}}$ mit der tabellarisch gegebenen Übergangsrelation ${\displaystyle \delta \!\,}$:

Weitere Informationen , ...

${\displaystyle q}$	${\displaystyle \delta (q,a)}$	${\displaystyle \delta (q,b)}$
${\displaystyle s_{0}\!\,}$	${\displaystyle \{s_{0}\!\,,s_{1}\}}$	${\displaystyle \{s_{0}\}\!\,}$
${\displaystyle s_{1}\!\,}$	${\displaystyle \emptyset }$	${\displaystyle \{s_{2}\}\!\,}$
${\displaystyle s_{2}\!\,}$	${\displaystyle \{s_{3}\}\!\,}$	${\displaystyle \emptyset }$
${\displaystyle s_{3}\!\,}$	${\displaystyle \emptyset }$	${\displaystyle \emptyset }$

Schließen

Eine graphische Darstellung des Ausgangsautomaten sieht folgendermaßen aus:

Nach obiger Konstruktion ergeben sich die Zustandsmenge ${\displaystyle Q\!\,'=\{S_{0}',S_{1}',S_{2}',S_{3}'\}}$ und die Übergangsfunktion ${\displaystyle \delta \!\,'}$ des äquivalenten deterministischen Automaten wie folgt:

Weitere Informationen , ...

${\displaystyle q'}$	${\displaystyle \delta '(q',a)}$	${\displaystyle \delta '(q',b)}$
${\displaystyle S_{0}\!\,'=\{s_{0}\}}$	${\displaystyle \{s_{0},s_{1}\}\!\,}$	${\displaystyle \{s_{0}\}\!\,}$
${\displaystyle S_{1}\!\,'=\{s_{0},s_{1}\}}$	${\displaystyle \{s_{0},s_{1}\}\!\,}$	${\displaystyle \{s_{0},s_{2}\}\!\,}$
${\displaystyle S_{2}\!\,'=\{s_{0},s_{2}\}}$	${\displaystyle \{s_{0},s_{1},s_{3}\}\!\,}$	${\displaystyle \{s_{0}\}\!\,}$
${\displaystyle S_{3}\!\,'=\{s_{0},s_{1},s_{3}\}}$	${\displaystyle \{s_{0},s_{1}\}\!\,}$	${\displaystyle \{s_{0},s_{2}\}\!\,}$

Schließen

Daraus leitet sich die Menge der Finalzustände ${\displaystyle F\!\,'=\{S_{3}'\}}$ ab, da nur ${\displaystyle S_{3}\!\,'=\{s_{0},s_{1},s_{3}\}}$ den Finalzustand ${\displaystyle s_{3}\!\,}$ des Ausgangsautomaten enthält. Insgesamt ergibt sich der deterministische Automat ${\displaystyle {\mathcal {A}}=(Q',\Sigma ,\delta ',s_{0}',F')}$, der folgende graphische Darstellung besitzt:

Automat zum regulären Ausdruck a(a|b)*b

NEA für den regulären Ausdruck ${\displaystyle a(a|b)^{*}b\!\,}$

Weitere Informationen , ...

${\displaystyle q'}$	${\displaystyle \delta '(q',a)}$	${\displaystyle \delta '(q',b)}$
${\displaystyle S_{0}'=\{s_{0}\}\!\,}$	${\displaystyle \{s_{1}\}\!\,}$	${\displaystyle \emptyset }$
${\displaystyle S_{1}'=\{s_{1}\}\!\,}$	${\displaystyle \{s_{1}\}\!\,}$	${\displaystyle \{s_{1},s_{2}\}\!\,}$
${\displaystyle S_{2}'=\{s_{1},s_{2}\}\!\,}$	${\displaystyle \{s_{1}\}\!\,}$	${\displaystyle \{s_{1},s_{2}\}\!\,}$
${\displaystyle 0=\emptyset }$	${\displaystyle \emptyset }$	${\displaystyle \emptyset }$

Schließen

DEA für den regulären Ausdruck ${\displaystyle a(a|b)^{*}b\!\,}$