33/216
\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$,\\
  there exists an algorithm and $C \ge 0$ such that for every 
  \begin{itemize}
    \item word $w$,
  \end{itemize} 
  the algorithm determines in at most \alert{$C \cdot |w|^3$ steps}
  \begin{itemize}
    \item whether $w \in L(G)$ (including a derivation tree if $w \in L(G)$).
  \end{itemize}
\end{frame}