Id: potenz.tex,v 1.1 2007-10-31 17:50:50 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' = 2Q (Potenzmenge - daher der Name)
-
(p', c, q') T'q' = {q | p p' : pAq}
-
S' = {S}
-
F' = {q' | q' Q' q' F }
Johannes Waldmann
2008-01-24