Automaten (Operationen: Komplement)

Eingabe: A₁ = (Σ, Q₁, I₁, δ₁, F₁),

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

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

• Q = 2^Q₁ (daher der Name)
• I = {I₁}, F = 2^{Q₁ $\setminus$ F₁}
• δ(c)(M) = ...

Korrektheit: ∀w∈Σ^* : w∈Lang(A)$\iff$w $\notin$Lang(A₁)

Komplexität: | Q| = 2^{| Q₁|} (hier: Zeit = Platz)