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$.

Beweis Korrektheit Potenzmengenkonstruktion

Sei $\mathcal{A}=(Q^\mathcal{A},A,\delta^\mathcal{A},I^\mathcal{A},F^\mathcal{A})$ NEA und $\mathcal{B}=(Q^\mathcal{B},A,\delta^\mathcal{B},q^\mathcal{B},F^\mathcal{B})$ DEA. Für $w\in A^*$ gilt, unter Zuhilfenahme des Lemmas Äquivalenz der Worttransitionsfunktion aus der Potenzmengenkonstruktion: