\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} \begin{exampleblock}{} For instance \emph{hannah} is a palindrome. \end{exampleblock} \pause\bigskip \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 \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}