\begin{solution}{3}
    \begin{enumerate}
        \setcounter{enumi}{1}
        \item See figure \ref{fig:9.3b} and \ref{fig:9.3b-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) [below right=of q2] {$q_4$};
                \node[state] (q5) [right=of q3] {$q_5$};
                \node[state] (q6) [above right=of q2] {$q_6$};
                \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
                \draw (q1) edge[loop above] node[above,align=left] {$a/a,R$\\$b/b,R$} (q1);
                \draw (q1) -- node[above,align=left] {$B/B,L$\\$X/X,L$\\$Y/Y,L$} ++ (q2);
                \draw (q2) -- node[above] {$a/X,R$} (q3);
                \draw (q2) -- node[below left] {$b/Y,R$} (q4);
                \draw (q3) edge[out=30,in=60,looseness=8] node[above,align=left] {$a/a,R$\\$b/b,R$\\$X/X,R$\\$Y/Y,R$} (q3);
                \draw (q3) -- node[above] {$B/a,L$} ++ (q5);
                \draw (q4) edge[loop below] node[below,align=left] {$a/a,R$\\$b/b,R$\\$X/X,R$\\$Y/Y,R$} (q4);
                \draw (q4) -- node[below right] {$B/b,L$} ++ (q5);
                \draw (q5) edge[loop above] node[above,align=left] {$a/a,L$\\$b/b,L$\\$X/X,L$\\$Y/Y,L$} (q5);
                \draw (q5) edge[out=270,in=270,looseness=2] node[below] {$B/B,R$} (q1);
                \draw (q2) -- node[above left] {$B/B,R$} ++ (q6);
                \draw (q6) edge[loop above] node[above,align=left] {$X/a,R$\\$Y/b,R$\\$a/a,L$\\$b/b,L$} (q6);
            \end{tikzpicture}
            \caption{The state machine of exercise 9.3b.}
            \label{fig:9.3b}
        \end{figure*}

        \begin{figure}[h]
            \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{clean}
				tape_9_3_b = [Just c \\ c <- fromString "abbaba"]
				ex_9_3_b :: TuringMachine Char
				ex_9_3_b = { alphabet = ['a', 'b', 'X', 'Y'],
				             inputs = ['a', 'b'],
				             transition = f }
				where
				    f :: Int (Maybe Char) -> TuringMachineMove Char
				    f 0 Nothing     = Step 1 Nothing    Right

				    f 1 (Just 'a')  = Step 1 (Just 'a') Right
				    f 1 (Just 'b')  = Step 1 (Just 'b') Right
				    f 1 c           = Step 2 c          Left

				    f 2 Nothing     = Step 6 Nothing    Right
				    f 2 (Just 'a')  = Step 3 (Just 'X') Right
				    f 2 (Just 'b')  = Step 4 (Just 'Y') Right

				    f 3 (Just c)    = Step 3 (Just c)   Right
				    f 3 Nothing     = Step 5 (Just 'a') Left

				    f 4 (Just c)    = Step 4 (Just c)   Right
				    f 4 Nothing     = Step 5 (Just 'b') Left

				    f 5 (Just c)    = Step 5 (Just c)   Left
				    f 5 Nothing     = Step 1 Nothing    Right

				    f 6 (Just 'X')  = Step 6 (Just 'a') Right
				    f 6 (Just 'Y')  = Step 6 (Just 'b') Right
				    f 6 (Just c)    = Step 6 (Just c)   Left

				    f _ _           = Halt
            \end{minted}
            \caption{The state machine of exercise 9.3b, for use with CleanTuringMachines.}
            \label{fig:9.3b-clean}
        \end{figure}

        We read $a$s and $b$s from the input string until the end in $q_1$. The last character is replaced by an $X$ or $Y$ for an $a$ or $b$, respectively, by $q_2$. Then, we place an $a$ or $b$ on the first blank on the right, depending on the last character of the input string. This happens in $q_3$ and $q_4$. We go back to the very beginning of the string in $q_5$, and repeat the process starting in $q_2$, but now stop reading at the beforelast character (and the one before that, and so on). If there are no more characters in the input string, we go to $q_6$ where we replace all $X$s by $a$s and all $Y$s by $b$s, after which we terminate.

    \item See figure \ref{fig:9.3c} and \ref{fig:9.3c-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) [above=of q2] {$q_3$};
                \node[state] (q4) [right=of q2] {$q_4$};
                \node[state] (q5) [below=2.5cm of q2] {$q_5$};
                \node[state] (q6) [right=of q5] {$q_6$};
                \node[state] (q7) [right=of q6] {$q_7$};
                \node[state] (q8) [right=of q7] {$q_8$};

                \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
                \draw (q1) edge[loop above] node[above,align=left] {$a/a,R$\\$b/b,R$} (q1);
                \draw (q1) -- node[above,align=left] {$X/X,L$\\$B/X,L$} ++ (q2);
                \draw (q2) edge[bend left] node[above left] {$a/X,R$} (q3);
                \draw (q3) edge[bend left] node[above right,align=left] {$B/a,R$\\$X/a,R$} (q2);
                \draw (q2) edge[bend left] node[above] {$b/X,R$} (q4);
                \draw (q4) edge[bend left] node[below,align=left] {$B/b,R$\\$X/b,R$} (q2);
                \draw (q2) -- node[left] {$B/B,L$} (q5);
                \draw (q5) edge[bend left] node[above,align=left] {$a/a,L$\\$b/b,L$} (q6);
                \draw (q6) edge[bend left] node[below] {$X/X,L$} (q5);
                \draw (q6) -- node[above] {$B/B,R$} (q7);
                \draw (q7) edge[loop above] node[above,align=left] {$a/a,R$\\$b/b,R$\\$X/X,R$} (q7);
                \draw (q7) -- node[above] {$B/B,L$} (q8);
                \draw (q8) edge[loop above] node[above,align=left] {$a/a,L$\\$b/b,L$\\$X/B,L$} (q8);
            \end{tikzpicture}
            \caption{The state machine of exercise 9.3c.}
            \label{fig:9.3c}
        \end{figure*}

        \begin{figure}[h]
            \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{clean}
				ex_9_3_c :: TuringMachine Char
				ex_9_3_c = { alphabet = ['a', 'b', 'X'],
				             inputs = ['a', 'b'],
				             transition = f }
				where
				    f :: Int (Maybe Char) -> TuringMachineMove Char
				    f 0 Nothing     = Step 1 Nothing    Right
				
				    f 1 (Just 'a')  = Step 1 (Just 'a') Right
				    f 1 (Just 'b')  = Step 1 (Just 'b') Right
				    f 1 (Just 'X')  = Step 2 (Just 'X') Left
				    f 1 Nothing     = Step 2 (Just 'X') Left
				
				    f 2 (Just 'a')  = Step 3 (Just 'X') Right
				    f 2 (Just 'b')  = Step 4 (Just 'X') Right
				    f 2 Nothing     = Step 5 Nothing    Left
				
				    f 3 (Just 'X')  = Step 2 (Just 'a') Right
				    f 3 Nothing     = Step 2 (Just 'a') Right
				
				    f 4 (Just 'X')  = Step 2 (Just 'b') Right
				    f 4 Nothing     = Step 2 (Just 'b') Right
				
				    f 5 (Just 'a')  = Step 6 (Just 'a') Left
				    f 5 (Just 'b')  = Step 6 (Just 'b') Left
				
				    f 6 (Just 'X')  = Step 5 (Just 'X') Left
				    f 6 (Just 'a')  = Step 2 (Just 'a') Right
				    f 6 (Just 'b')  = Step 2 (Just 'b') Right
				    f 6 Nothing     = Step 7 Nothing    Right
				
				    f 7 (Just c)    = Step 7 (Just c)   Right
				    f 7 Nothing     = Step 8 Nothing    Left
				
				    f 8 (Just 'X')  = Step 8 Nothing    Left
				    f 8 (Just c)    = Step 8 (Just c)   Left
				
				    f _ _           = Halt
            \end{minted}
            \caption{The state machine of exercise 9.3c, for use with CleanTuringMachines.}
            \label{fig:9.3c-clean}
        \end{figure}
        
        The idea would be to first move the last character to the right, then the last $2$ characters of the new string, then the last $3$ characters of that string, et cetera., until we are back at the leftmost position. This could be recognised by putting a marker there, if needed.
            
    \end{enumerate}
\end{solution}