\begin{slide}{Top-down oder Bottom-up}

\begin{itemize}
\item
  Bottom-up: Eingabe verarbeiten (akzeptieren): $F\to 0,0\vee 1\to 1,\ldots$,
\item
  Top-down: Ausgabe erzeugen: $1 \to 0 \vee 1, 0 \to F$
\item
  beide Sichtweisen sind äquivalent (Pfeile herumdrehen)
\item
  \dots für nichtdeterministische Automaten
\item
  was heißt \emph{Determinismus}?
\end{itemize}

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.

\end{slide}
