\begin{solution}{4}
    See figure \ref{fig:9.4} and \ref{fig:9.4-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) [right=of q4] {$q_5$};
            \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
            \draw (q1) -- node[above] {$a/a,R$} ++ (q2);
            \draw (q2) -- node[above] {$a/a,R$} ++ (q3);
            \draw (q3) -- node[above] {$a/a,R$} ++ (q4);
            \draw (q4) -- node[above] {$c/c,L$} ++ (q5);
            \draw (q1) edge[loop above] node[above,align=left] {$B/B,R$\\$b/b,R$\\$c/c,R$} (q1);
            \draw (q2) edge[bend left] node[below,align=left] {$B/B,R$\\$b/b,R$\\$c/c,R$} (q1);
            \draw (q3) edge[bend right] node[above,align=left] {$B/B,R$\\$b/b,R$\\$c/c,R$} (q1);
            \draw (q4) edge[bend left] node[below,align=left] {$B/B,R$\\$b/b,R$} (q1);
            \draw (q4) edge[loop above] node[above,align=left] {$a/a,R$} (q4);
            \draw (q5) edge[loop above] node[above,align=left] {$a/a,L$\\$b/b,L$\\$c/c,L$} (q5);
        \end{tikzpicture}
        \caption{The state machine of exercise 9.4.}
        \label{fig:9.4}
    \end{figure*}

    \begin{figure}[h]
        \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{clean}
			tape_9_4 = [Just c \\ c <- fromString "baaabbaaacabab"]
			ex_9_4 :: TuringMachine Char
			ex_9_4 = { alphabet = ['a', 'b', 'c'],
			           inputs = ['a', 'b', 'c'],
			           transition = f }
			where
			    f :: Int (Maybe Char) -> TuringMachineMove Char
			    f 0 Nothing     = Step 1 Nothing    Right
			
			    f 1 (Just 'a')  = Step 2 (Just 'a') Right
			    f 1 c           = Step 1 c          Right
			
			    f 2 (Just 'a')  = Step 3 (Just 'a') Right
			    f 2 c           = Step 1 c          Right
			
			    f 3 (Just 'a')  = Step 4 (Just 'a') Right
			    f 3 c           = Step 1 c          Right
			
			    f 4 (Just 'a')  = Step 4 (Just 'a') Right
			    f 4 (Just 'c')  = Step 5 (Just 'c') Left
			    f 4 c           = Step 1 c          Right
			
			    f 5 (Just c)    = Step 5 (Just c)   Left
			
			    f _ _           = Halt
        \end{minted}
        \caption{The state machine of exercise 9.4, for use with CleanTuringMachines.}
        \label{fig:9.4-clean}
    \end{figure}

    The intuition is that in state $q_i$ we have read $i-1$ consecutive $a$s, for $i\in\{1,2,3,4\}$, or even more in the case of $q_4$. Hence, the only possibility to let the machine terminate should be when we read a $c$ in $q_4$. This is done in $q_5$, which also has the function of bringing back the tape head to position $0$.
\end{solution}

