\begin{frame}{Exercise}
  \begin{exampleblock}{}
    Construct a Turing machine accepting all words of \emph{odd} length over the alphabet $\Sigma = \{a,b\}$.
    \pause    
    \begin{center}
      \begin{tikzpicture}[default,node distance=25mm,->,s/.style={minimum size=5mm}]
        \node (q0) [state,s] {$q_0$}; \draw ($(q0) + (-8mm,0mm)$) -- (q0); 
        \node (q1) [state,s,right of=q0] {$q_1$};
        \node (q2) [fstate,s,right of=q1] {$q_2$};
      
        \draw (q0) to[bend left=20] node [label,above,align=center] {$a/a$ $R$\\$b/b$ $R$} (q1);
        \draw (q1) to[bend left=20] node [label,below,align=center] {$a/a$ $R$\\$b/b$ $R$} (q0);
        \draw (q1) to node [label,above] {$\Box/\Box$ $R$} (q2);
      \end{tikzpicture}
      \vspace{-1ex}
    \end{center}
    Multiple labels on an arrow are short for multiple transitions.
  \end{exampleblock}
\end{frame}

\themex{Extensions of Turing Machines}