\begin{frame}{Example} \begin{exampleblock}{} Consider the following instance of the MPCP: \begin{talign} w_1 &= 11 & w_2 &= 1 \\ v_1 &= 1 & v_2 &= 11 \end{talign} It reduces to the following PCP problem: \begin{talign} y_0 &= @ \$1\$1\$ & y_1 &= 1\$1\$ & y_2 &= 1\$ & y_3 &= \# \\ z_0 &= @ \$1 & z_1 &= \$1 & z_2 &= \$1\$1 & z_3 &= \$\# \end{talign} \pause Example solution MPCP: \begin{talign} w_1 w_2 = 111 = v_1 v_2 \end{talign} Corresponding solution PCP: \begin{talign} y_0 y_2 y_3 = @ \$1\$1\$ 1\$ \# = z_0 z_2 z_3 \end{talign} \end{exampleblock} \pause\medskip In general: the original MPCP instance has a solution\\ \hfill $\iff$ the resulting PCP instance has a solution \end{frame} \themex{Undecidable Properties of Context-Free Languages}