ex9-1.tex


1
2
3
4
5
6
7
8
9
10
11
12
13

\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 Todo %todo
        \item All $b$s in the input string are replaced by $c$s. All $c$s are replace 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}