Automaten (Operationen: Komplement)

Eingabe: A1 = (Σ, Q1, I1, δ1, F1),

Ausgabe: A mit Lang(A) = Σ* $ \setminus$ Lang(A1)

Lösung durch Potenzmengen-Konstruktion: A = (Σ, Q, I, δ, F) mit

Korrektheit: wΣ* : w∈Lang(A)$ \iff$w $ \notin$Lang(A1)


Komplexität: | Q| = 2| Q1| (hier: Zeit = Platz)



2014-07-06