\begin{frame}{Inherently Ambiguous Languages}
  \begin{block}{}
    A language $L$ is \emph{inherently ambiguous} if 
    \begin{itemize}
      \item $L$ is context-free, and
      \item \emph{every} grammar $G$ with $L(G) = L$ is ambiguous.
    \end{itemize}
  \end{block}
  \pause
  
  \begin{exampleblock}{}
    The following context-free language is inherently ambiguous
    \begin{talign}
      \{ \; a^n b^m c^\ell \; | \; n=m \; \vee \; m=\ell \; \}
    \end{talign}
    It is generated by the following (ambiguous) grammar
    \begin{talign}
        S &\to A \; | \; B 
      & A &\to Ac \; | \; C
      & B &\to aB \; | \; D \\
      && C &\to aCb \; | \; \lambda 
      & D &\to bDc \; | \; \lambda 
    \end{talign}
  \end{exampleblock}
  \pause\smallskip
  
  \begin{exampleblock}{Exercise}
    Find two derivation trees for the word $abc$.  
  \end{exampleblock}
  
  % \visible<2>{
  % Twee afleidingsbomen voor $abc$ zijn:
  % \[
  % \begin{array}{rccclrcccl}
  %  & & S & & &                                & & S \\
  %  & & \downarrow & & &                       & & \downarrow \\
  %  & & A & & &                                & & B \\
  %  & & \downarrow & \searrow & &              & \swarrow & \downarrow \\
  %  & & A & & c \hspace*{2cm} &                a & & B \\
  %  & & \downarrow & & &                       & & \downarrow \\
  %  & & C & & &                                & & D \\
  %  & \swarrow & \downarrow & \searrow & &     & \swarrow & \downarrow & \searrow \\
  % a & & C & & b &                            b & & D & & c \\
  %  & & \downarrow & & &                       & & \downarrow \\
  %  & & \lambda & & &                          & & \lambda
  % \end{array}
  % \]
  % }

\end{frame}

\themex{Parsing}