\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}