Automaten (Operationen: Projektion)

Eingabe: Automat A₁ = (Σ^k, Q₁, I₁, δ₁, F₁), Zahl i

Ausgabe: A mit Lang(A) = Lang(proj_i(A₁))

Lösung: A = (Σ^k-1, Q, I, δ, F) mit

• Q = Q₁, I = I₁, F = F₁
• δ(c)(p, q) = ...

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

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