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

    Only the first two questions are decidable.
    Remove all $\lambda$ and unit productions.
    \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.
  \structure{Surprisingly} all other questions are undecidable.