\begin{solution}{1}
    \begin{enumerate}
        \item \begin{align*}
                & q_0BaabcaB \vdash Bq_1aabcaB \\\vdash& Baq_1abcaB \vdash Baaq_1bcaB \\\vdash& Baacq_1caB \vdash Baaccq_1aB \\\vdash& Baaccaq_1B \vdash Baaccq_2aB \\\vdash& Baacq_2ccB \vdash Baaq_2cbcB \\\vdash& Baq_2abbcB \vdash Bq_2acbbcB \\\vdash& q_2BccbbcB.
            \end{align*}
        \item \begin{align*}
                & q_0BbcbcB \vdash Bq_1bcbcB \\\vdash& Bcq_1cbcB \vdash Bccq_1bcB \\\vdash& Bcccq_1cB \vdash Bccccq_1B \\\vdash& Bcccq_2cB \vdash Bccq_2cbB \\\vdash& Bcq_2cbbB \vdash Bq_2cbbbB \\\vdash& q_2BbbbbB.
            \end{align*}
        \item See figure \ref{fig:9.1c}.
            
            \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$};
                    \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
                    \draw (q1) edge[loop above] node[above,align=left] {$c/c,R$\\$b/c,R$\\$a/a,R$} (q1);
                    \draw (q1) -- node[above] {$B/B,L$} ++ (q2);
                    \draw (q2) edge[loop above] node[above,align=left] {$c/b,L$\\$a/c,L$} (q2);
                \end{tikzpicture}
                \caption{The state machine of exercise 9.1c.}
                \label{fig:9.1c}
            \end{figure*}
        \item All $a$s in the input string are replaced by $c$s. All $c$s are replaced by $b$s. All $b$s are left intact. The machine terminates in a normal fashion with the tape head on position $0$.
    \end{enumerate}
\end{solution}

