Ex 9.1 / 9.2

3 files changed, 51 insertions, 4 deletions

diff --git a/ex9-1.tex b/ex9-1.tex
index c416fdb..c06f4f0 100644
--- a/ex9-1.tex
+++ b/ex9-1.tex
@@ -1,13 +1,28 @@
 \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.
+                & 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.
+                & 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$.
+        \item See figure \ref{fig:9.1c}.
+            
+            \begin{figure*}[t]
+                \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}
 
diff --git a/ex9-2.tex b/ex9-2.tex
new file mode 100644
index 0000000..5755daf
--- /dev/null
+++ b/ex9-2.tex
@@ -0,0 +1,28 @@
+\begin{solution}{2}
+    \begin{enumerate}
+        \item \begin{align*}
+                & q_0BabcabB \vdash Bq_1abcabB \\\vdash& Baq_1bcabB \vdash Babq_1cabB \\\vdash& Baq_2bcabB \vdash Bq_2aacabB \\\vdash& q_2BbacabB.
+            \end{align*}
+        \item \begin{align*}
+                & q_0BababB \vdash Bq_1ababB \\\vdash& Baq_1babB \vdash Babq_1abB \\\vdash& Babaq_1bB \vdash Bababq_1B \\\vdash& BababBq_1B \dots
+            \end{align*}
+        \item See figure \ref{fig:9.2c}.
+            
+            \begin{figure*}[t]
+                \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] {$b/b,R$\\$a/a,R$\\$B/B,R$} (q1);
+                    \draw (q1) -- node[above] {$c/c,L$} ++ (q2);
+                    \draw (q2) edge[loop above] node[above,align=left] {$b/a,L$\\$a/b,L$} (q2);
+                \end{tikzpicture}
+                \caption{The state machine of exercise 9.2c.}
+                \label{fig:9.2c}
+            \end{figure*}
+        \item Replace all $a$s with $b$s and vice versa on the left of the first $c$, if it exists. If it does not exist, the string is not modified but the machine never terminates.
+    \end{enumerate}
+\end{solution}
+
diff --git a/exercises.tex b/exercises.tex
index ce25ccd..0339778 100644
--- a/exercises.tex
+++ b/exercises.tex
@@ -17,6 +17,9 @@
 \fancyfoot[C]{Copyright \textcopyright 2015 Camil Staps}
 \pagestyle{fancy}
 
+\usepackage{tikz}
+\usetikzlibrary{positioning,arrows,automata}
+
 \usepackage{amsmath}
 
 % Solution environment
@@ -34,6 +37,7 @@
 \setcounter{section}{8}
 \section{Turing machines}
 \input{ex9-1.tex}
+\input{ex9-2.tex}
 
 \end{document}