Top-down oder Bottom-up

• Bottom-up: Eingabe verarbeiten (akzeptieren): F$\to$0, 0 $\vee$ 1$\to$1,...,
• Top-down: Ausgabe erzeugen: 1$\to$0 $\vee$ 1, 0$\to$F
• beide Sichtweisen sind äquivalent (Pfeile herumdrehen)
• ...für nichtdeterministische Automaten
• was heißt Determinismus?

Ein Bottom-Up-Automat ($\Sigma$, Q, F, R) heißt deterministisch, wenn in R alle linken Regelseiten verschieden sind.

Ein Top-Down-Automat ($\Sigma$, Q, F, R) heißt deterministisch, wenn?

Es gibt Baumsprachen, die einen deterministischen bottom-up-, aber keine deterministischen top-down-Automaten besitzen.