\begin{solution}{5}
    \begin{enumerate}
        \item See figure \ref{fig:9.5a}.

            \begin{figure*}[p]
                \centering
                \begin{tikzpicture}[->, node distance=2cm]
                    \node[state,initial] (q0) {$q_0$};
                    \node[state] (q1) [right=of q0] {$q_1$};
                    \node[state] (q2) [right=of q1] {$q_2$};
                    \node[state] (q3) [right=of q2] {$q_3$};
                    \node[state] (q4) [below=of q1] {$q_4$};
                    \node[state,accepting] (q5) [right=of q4] {$q_5$};
                    \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
                    \draw (q1) -- node[above] {$a/X,R$} ++ (q2);
                    \draw (q2) edge[loop above] node[above,align=left] {$a/a,R$\\$Y/Y,R$} (q2);
                    \draw (q2) -- node[above] {$b/Y,L$} ++ (q3);
                    \draw (q3) edge[loop right] node[right,align=left] {$a/a,L$\\$Y/Y,L$} (q3);
                    \draw (q3) edge[bend right, out=300, in=240, looseness=1.3] node[above] {$X/X,R$} (q1);
                    \draw (q1) -- node[left,align=right] {$B/B,R$\\$Y/Y,R$} ++ (q4);
                    \draw (q4) edge[loop left] node[left] {$b/b,R$} (q4);
                    \draw (q4) -- node[above] {$B/B,R$} ++ (q5);
                \end{tikzpicture}
                \caption{The state machine of exercise 9.5a.}
                \label{fig:9.5a}
            \end{figure*}
            
            The intuition is: for the first $a$ that we read, mark it with $X$ and mark the next $b$ we see with $Y$. Go back to the beginning and repeat. When we read a $Y$ instead of an $a$, we have finished the $a^i$ part of the string, and we can go to a final state. The machine should check that there is a $b$ for every $a$ and that the $a$s and $b$s are consecutive. 

        \setcounter{enumi}{2}

        \item See figure \ref{fig:9.5c} and \ref{fig:9.5c-clean}.

            \begin{figure*}[p]
                \centering
                \begin{tikzpicture}[->, node distance=2cm]
                    \node[state,initial] (q0) {$q_0$};
                    \node[state] (q1) [right=of q0] {$q_1$};
                    \node[state] (q2) [right=of q1] {$q_2$};
                    \node[state] (q3) [right=of q2] {$q_3$};
                    \node[state] (q4) [right=of q3] {$q_4$};
                    \node[state] (q5) [below=of q1] {$q_5$};
                    \node[state,accepting] (q6) [right=of q5] {$q_6$};
                    \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
                    \draw (q1) edge[loop above] node[above,align=left] {$b/b,R$\\$X/X,R$} (q1);
                    \draw (q1) -- node[above] {$a/X,L$} ++ (q2);
                    \draw (q2) edge[loop above] node[above,align=left] {$b/b,L$\\$X/X,L$} (q2);
                    \draw (q2) -- node[above] {$B/B,R$} ++ (q3);
                    \draw (q3) edge[loop above] node[above,align=left] {$a/a,R$\\$X/X,R$} (q3);
                    \draw (q3) -- node[above] {$b/X,R$} ++ (q4);
                    \draw (q4) edge[loop right] node[right,align=left] {$a/a,L$\\$b/b,L$\\$X/X,L$} (q4);
                    \draw (q4) edge[bend right, out=300, in=240, looseness=1.2] node[above] {$B/B,R$} (q1);
                    \draw (q1) -- node[left] {$B/B,L$} ++ (q5);
                    \draw (q5) edge[loop left] node[left] {$X/X,L$} (q5);
                    \draw (q5) -- node[above] {$B/B,R$} ++ (q6);
                \end{tikzpicture}
                \caption{The state machine of exercise 9.5c.}
                \label{fig:9.5c}
            \end{figure*}

            \begin{figure}[h]
                \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{text}
					tape_9_5_c = [Just c \\ c <- fromString "abbabbabaa"]
					ex_9_5_c :: TuringMachine Char
					ex_9_5_c = { alphabet = ['a', 'b'],
					             inputs = ['a', 'b'],
					             transition = f }
					where
					    f :: Int (Maybe Char) -> TuringMachineMove Char
					    f 0 Nothing     = Step 1 Nothing    Right
					
					    f 1 (Just 'a')  = Step 2 (Just 'X') Left
					    f 1 (Just c)    = Step 1 (Just c)   Right
					    f 1 Nothing     = Step 5 Nothing    Left
					
					    f 2 (Just 'b')  = Step 2 (Just 'b') Left
					    f 2 (Just 'X')  = Step 2 (Just 'X') Left
					    f 2 Nothing     = Step 3 Nothing    Right
					
					    f 3 (Just 'X')  = Step 3 (Just 'X') Right
					    f 3 (Just 'a')  = Step 3 (Just 'a') Right
					    f 3 (Just 'b')  = Step 4 (Just 'X') Right
					
					    f 4 (Just c)    = Step 4 (Just c)   Left
					    f 4 Nothing     = Step 1 Nothing    Right
					
					    f 5 (Just 'X')  = Step 5 (Just 'X') Left
					    f 5 Nothing     = Step 6 Nothing    Right
					
					    f _ _           = Halt
                \end{minted}
                \caption{The state machine of exercise 9.5c, for use with CleanTuringMachines.}
                \label{fig:9.5c-clean}
            \end{figure}
            
            The intuition is: find a $b$ for every $a$, mark both with $X$. Repeat until there are no $a$s left. Then check that there are also no $b$s left.
    \end{enumerate}
\end{solution}