Automaten (Operationen: Komplement)

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

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

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

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

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

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