\begin{frame}{Parsing}
  \begin{goal}{}
    \emph{Parsing} is the search for a derivation tree for a given word.
  \end{goal}
  \pause\bigskip

  \begin{block}{Theorem}
    For context-free grammars, 
    parsing is possible in \alert{$O(|w|^3)$} time.\\
    (Here $|w|$ is the length of the input word.)
  \end{block}
  \pause\medskip
  
  For every context-free grammar $G$:
  \begin{itemize}
    \item 
      there exists an algorithm and $C \ge 0$ such that  
    \item for every word $w$,
          the algorithm determines in at most 
          \begin{center}
            \alert{$C \cdot |w|^3$ steps}
          \end{center}
          whether $w \in L(G)$ and a derivation tree if $w \in L(G)$.
  \end{itemize}
\end{frame}