Automaten (Operationen: Projektion)

Eingabe: Automat A1 = (Σk, Q1, I1, δ1, F1) mathend000#, Zahl i mathend000#

Ausgabe: A mathend000# mit Lang(A) = Lang(proji(A1)) mathend000#

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

Korrektheit: wΣ* : w∈Lang(A)$ \iff$wLang(proji(A1)) mathend000#


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



2014-03-31