Potenzmengen-Konstruktion

Id: potenz.tex,v 1.2 2004/12/14 12:36:40 waldmann Exp

• Eingabe: ein (nicht-det.) Automat A = (Q, S, F, T)
• Ausgabe: ein vollst. det. Automat A' mit L(A') = L(A).

Idee: betrachten Mengen von erreichbaren Zuständen

A' = (Q', S', F', T') mit

• Q' = 2^Q (Potenzmenge - daher der Name)
• (p', c, q') $\in$ T'$\iff$q' = {q | $\exists$p $\in$ p' : p$\;\stackrel{c}{\to}\;$_Aq}
• S' = {S}
• F' = {q' | q' $\in$ Q' $\wedge$ q' $\cap$ F $\neq$ $\emptyset$}