\begin{frame}{Ambiguity of Context-Free Grammars}
  \begin{goal}{Theorem}
    Ambiguity of context-free grammars is undecidable.
  \end{goal}
  \pause
  
  \begin{proof}
    We reduce the PCP to the above problem.
    \pause\medskip
        
    Given a PCP instance $X$: \alert{$(w_1,v_1),\ldots,(w_n,v_n)$}.
    \pause\medskip
    
    We define a context-free grammar $G$:
    \begin{talign}
      \alert{S \to S_1 \mid S_2} 
      && \alert{S_1} &\alert{\rightarrow w_i S_1 \langle i \rangle \mid w_i \,\#\, \langle i \rangle} \\ 
      && \alert{S_2} &\alert{\rightarrow v_i\, S_2 \langle i \rangle \mid v_i\, \,\#\, \langle i \rangle}
    \end{talign}
    for $1 \le i \le n$. Here $\#$, $\langle$ and $\rangle$ are fresh symbols.
    \pause\medskip
    
    Then $G$ is ambiguous \;$\iff$\; the PCP $X$ has a solution.
  \end{proof}
\end{frame}