39/110
\begin{frame}{Exercises (2)}
\begin{block}{}
A word $w = a_1a_2\cdots a_n$ is called \emph{palindrome} if $w = w^R$, that is
\begin{talign}
a_1a_2\cdots a_n = a_n\cdots a_2a_1
\end{talign}
\end{block}
\pause\bigskip

(Individual, 2 minutes)
\begin{exampleblock}{}
\emph{Find a grammar} $G$ that generates all palindromes over the alphabet $\Sigma = \{a,b\}$.
In other words
\begin{talign}
L(G) = \{\,w \in \Sigma^* \mid \text{$w$ is a palindrome}\}
\end{talign}
\end{exampleblock}
\pause\bigskip

(Groups of two, 3 minutes)
\begin{exampleblock}{}
\emph{Find a grammar} $G$ that generates all non-palindromes over the alphabet $\Sigma = \{a,b\}$.
In other words
\begin{talign}
L(G) = \{\,w \in \Sigma^* \mid \text{$w$ is \alert{not} a palindrome}\,\}
\end{talign}
\end{exampleblock}
\end{frame}