Potenzmengenkonstruktion
Einfache Sprache
Def. Potenzmengenkonstruktion
Sei $\mathcal{A}=(Q^\mathcal{A},A,\delta^\mathcal{A},I^\mathcal{A},F^\mathcal{A})$ NEA.Wir definieren den Potenzmengenautomat $\mathcal{B}=(Q^\mathcal{B},A,\delta^\mathcal{B},q^\mathcal{B},F^\mathcal{B})$ mit:
- $Q^\mathcal{B}=\mathcal{P}(Q^\mathcal{A})$
- $\delta^\mathcal{B}(R,x)=\underset{q\in R}\bigcup \delta^\mathcal{A}(q,x)$ mit $R\in\mathcal{P}(Q^\mathcal{A})$, d.h. $R\subseteq Q^\mathcal{A},x\in A$.
- $q^\mathcal{B}=I^\mathcal{A}$
- $F^\mathcal{B}=\{R\subseteq Q^\mathcal{A}|R\cap F^\mathcal{A}\neq\emptyset\}$ Der Potenzmengenautomat ist ein DEA der die gleich Sprache erkennt wie $\mathcal A$.