Eingabe: A1 = (Σ, Q1, I1, δ1, F1),
Ausgabe: A mit Lang(A) = Σ* Lang(A1)
Lösung durch Potenzmengen-Konstruktion: A = (Σ, Q, I, δ, F) mit
Korrektheit: ∀w∈Σ* : w∈Lang(A)w Lang(A1)
Komplexität: | Q| = 2| Q1| (hier: Zeit = Platz)