Automaten (Operationen: Projektion)

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

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

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

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

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

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