\begin{frame}{Basic Questions about Context-Free Grammars}
  \begin{goal}{}
    Given context-free grammar $G$ and $H$.
    \medskip
    
    Which of the following questions are \emph{decidable}?
    \begin{enumerate}\setlength{\itemsep}{0pt}
    \pause
      \item Given $w \in \Sigma^*$, do we have $w \in L(G)$\,?
    \pause
      \item Is $L(G)$ empty\,?
    \pause
      \item Does $L(G) = \Sigma^*$ hold\,?
    \pause
      \item Does $L(G)$ contain a palindrome ($w = w^R$)\,?\\
    \pause
      \item Does $L(G) = L(H)$ hold\,?
    \pause
      \item Is $L(G) \cap L(H)$ empty\,?
    \end{enumerate}
  \end{goal}
  \pause

  \begin{alertblock}{}
    Only the first two questions are decidable.
  \end{alertblock}
  \pause
  \begin{block}{}\setlength{\itemsep}{0pt}
    Remove all $\lambda$ and unit productions.
    \begin{enumerate}
    \item $\{\, v \mid S \Rightarrow^* v,\; |v|\leq|w| \,\}$ can be computed in finite time.
    \item $L(G)$ is empty $\iff$ starting variable is useless.
    \end{enumerate}
  \end{block}
  \pause
  \structure{Surprisingly} all other questions are undecidable.
  \bigskip
\end{frame}