\begin{frame}{Exercise (2)}
  \begin{exampleblock}{}
    Use the pumping lemma to \emph{show that} 
    \begin{talign}
      L = \{\,a^{2^k}\mid k\geq 0\,\}
    \end{talign}
    \emph{is not regular}.
    \pause
    Assume that $L$ was regular.
    \pause\medskip
    
    By the pumping lemma there exists $m>0$ such that
    \begin{talign}
      \mpause[1]{a^{2^m}} = xyz
    \end{talign}
    with $|xy| \leq m$, $|y| \geq 1$, and $xy^i z \in L$ for every $i \geq 0$.
    \pause\pause\medskip
    
    Since $|xy| \leq m$ and $|y|\geq 1$, it follows that
    \begin{talign}
      x=a^{\,j} &&\text{and}&& y = a^k
    \end{talign}
    with $j\geq 0$, $k\geq 1$ and $j + k \le m$.
    \pause\medskip
    
    We have $k \le m < 2^m$ \pause and hence $2^m < 2^m + k < 2^{m+1}$. 
    \pause\medskip
    
    Contradiction: $xy^2z = a^{2^m+k} \not\in L$! \pause Thus $L$ is not regular.\qed
  \end{exampleblock}
\end{frame}