From c3f0c43e5d0bb96896c626fa9c66556ad3a18a31 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Fri, 4 Sep 2015 12:44:53 +0200
Subject: Ex 9.5/9.6

---
 ex9-5.tex     | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 ex9-6.tex     | 34 +++++++++++++++++++++-
 exercises.icl | 45 ++++++++++++++++++++++++++++-
 3 files changed, 166 insertions(+), 6 deletions(-)

diff --git a/ex9-5.tex b/ex9-5.tex
index c3a56b7..183213c 100644
--- a/ex9-5.tex
+++ b/ex9-5.tex
@@ -1,14 +1,99 @@
 \begin{solution}{5}
     \begin{enumerate}
-        \item The intuition would be: for the first $a$ that we read, mark it with $X$ and mark the next $b$ we see with $Y$. Go back to the beginning and repeat. When we read a $Y$ instead of an $a$, we have finished the $a^i$ part of the string, and we can go to a final state. The machine should check that there is a $b$ for every $a$ and that the $a$s and $b$s are consecutive. 
+        \item See figure \ref{fig:9.5a}.
+
+            \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=of q1] {$q_4$};
+                    \node[state,accepting] (q5) [right=of q4] {$q_5$};
+                    \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
+                    \draw (q1) -- node[above] {$a/X,R$} ++ (q2);
+                    \draw (q2) edge[loop above] node[above,align=left] {$a/a,R$\\$Y/Y,R$} (q2);
+                    \draw (q2) -- node[above] {$b/Y,L$} ++ (q3);
+                    \draw (q3) edge[loop right] node[right,align=left] {$a/a,L$\\$Y/Y,L$} (q3);
+                    \draw (q3) edge[bend right, out=300, in=240, looseness=1.3] node[above] {$X/X,R$} (q1);
+                    \draw (q1) -- node[left,align=right] {$B/B,R$\\$Y/Y,R$} ++ (q4);
+                    \draw (q4) edge[loop left] node[left] {$b/b,R$} (q4);
+                    \draw (q4) -- node[above] {$B/B,R$} ++ (q5);
+                \end{tikzpicture}
+                \caption{The state machine of exercise 9.5a.}
+                \label{fig:9.5a}
+            \end{figure*}
             
-            %todo draw machine
+            The intuition is: for the first $a$ that we read, mark it with $X$ and mark the next $b$ we see with $Y$. Go back to the beginning and repeat. When we read a $Y$ instead of an $a$, we have finished the $a^i$ part of the string, and we can go to a final state. The machine should check that there is a $b$ for every $a$ and that the $a$s and $b$s are consecutive. 
 
         \setcounter{enumi}{2}
 
-        \item The intuition would be: find a $b$ for every $a$, mark both with $X$. Repeat until there are no $a$s left. Then check that there are also no $b$s left.
+        \item See figure \ref{fig:9.5c} and \ref{fig:9.5c-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) [below=of q1] {$q_5$};
+                    \node[state,accepting] (q6) [right=of q5] {$q_6$};
+                    \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
+                    \draw (q1) edge[loop above] node[above,align=left] {$b/b,R$\\$X/X,R$} (q1);
+                    \draw (q1) -- node[above] {$a/X,L$} ++ (q2);
+                    \draw (q2) edge[loop above] node[above,align=left] {$b/b,L$\\$X/X,L$} (q2);
+                    \draw (q2) -- node[above] {$B/B,R$} ++ (q3);
+                    \draw (q3) edge[loop above] node[above,align=left] {$a/a,R$\\$X/X,R$} (q3);
+                    \draw (q3) -- node[above] {$b/X,R$} ++ (q4);
+                    \draw (q4) edge[loop right] node[right,align=left] {$a/a,L$\\$b/b,L$\\$X/X,L$} (q4);
+                    \draw (q4) edge[bend right, out=300, in=240, looseness=1.2] node[above] {$B/B,R$} (q1);
+                    \draw (q1) -- node[left] {$B/B,L$} ++ (q5);
+                    \draw (q5) edge[loop left] node[left] {$X/X,L$} (q5);
+                    \draw (q5) -- node[above] {$B/B,R$} ++ (q6);
+                \end{tikzpicture}
+                \caption{The state machine of exercise 9.5c.}
+                \label{fig:9.5c}
+            \end{figure*}
 
-            %todo draw machine
+            \begin{figure}[h]
+                \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{text}
+					tape_9_5_c = [Just c \\ c <- fromString "abbabbabaa"]
+					ex_9_5_c :: TuringMachine Char
+					ex_9_5_c = { alphabet = ['a', 'b'],
+					             inputs = ['a', 'b'],
+					             transition = f }
+					where
+					    f :: Int (Maybe Char) -> TuringMachineMove Char
+					    f 0 Nothing     = Step 1 Nothing    Right
+					
+					    f 1 (Just 'a')  = Step 2 (Just 'X') Left
+					    f 1 (Just c)    = Step 1 (Just c)   Right
+					    f 1 Nothing     = Step 5 Nothing    Left
+					
+					    f 2 (Just 'b')  = Step 2 (Just 'b') Left
+					    f 2 (Just 'X')  = Step 2 (Just 'X') Left
+					    f 2 Nothing     = Step 3 Nothing    Right
+					
+					    f 3 (Just 'X')  = Step 3 (Just 'X') Right
+					    f 3 (Just 'a')  = Step 3 (Just 'a') Right
+					    f 3 (Just 'b')  = Step 4 (Just 'X') Right
+					
+					    f 4 (Just c)    = Step 4 (Just c)   Left
+					    f 4 Nothing     = Step 1 Nothing    Right
+					
+					    f 5 (Just 'X')  = Step 5 (Just 'X') Left
+					    f 5 Nothing     = Step 6 Nothing    Right
+					
+					    f _ _           = Halt
+                \end{minted}
+                \caption{The state machine of exercise 9.5c, for use with CleanTuringMachines.}
+                \label{fig:9.5c-clean}
+            \end{figure}
+            
+            The intuition is: find a $b$ for every $a$, mark both with $X$. Repeat until there are no $a$s left. Then check that there are also no $b$s left.
     \end{enumerate}
 \end{solution}
 
diff --git a/ex9-6.tex b/ex9-6.tex
index 58f14d2..c1ed1a3 100644
--- a/ex9-6.tex
+++ b/ex9-6.tex
@@ -1,4 +1,36 @@
 \begin{solution}{6}
-    This is not much different from 5a. %todo
+    See figure \ref{fig:9.6}.
+
+    \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=of q1] {$q_4$};
+            \node[state] (q5) [below=of q4] {$q_5$};
+            \node[state] (qf) [right=of q4] {$q_f$};
+            \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
+            \draw (q1) -- node[above] {$a/X,R$} ++ (q2);
+            \draw (q2) edge[loop above] node[above,align=center] {$a/a,R$\\$Y/Y,R$} (q2);
+            \draw (q2) -- node[above] {$b/Y,L$} ++ (q3);
+            \draw (q3) edge[loop right] node[right,align=left] {$a/a,L$\\$Y/Y,L$} (q3);
+            \draw (q3) edge[bend right, out=300, in=240, looseness=1.3] node[above] {$X/X,R$} (q1);
+            \draw (q1) -- node[left,align=right] {$B/B,R$\\$Y/Y,R$} ++ (q4);
+            \draw (q4) edge[loop left] node[left] {$b/b,R$} (q4);
+            \draw (q4) -- node[left] {$B/B,R$} ++ (q5);
+
+            \draw (q1) -- node[above right] {$b/b,R$} ++ (qf);
+            \draw (q2) -- node[above right,align=left] {$B/B,R$\\$X/X,R$} ++ (qf);
+            \draw (q3) -- node[below right,align=left] {$b/b,R$\\$B/B,R$} ++ (qf);
+            \draw (q4) -- node[below,align=center] {$a/a,R$\\$X/X,R$\\$Y/Y,R$} ++ (qf);
+            \draw (qf) edge[out=300,in=330,looseness=8] node[below right,align=left] {$B/B,R$\\$a/a,R$\\$b/b,R$\\$X/X,R$\\$Y/Y,R$} (qf);
+        \end{tikzpicture}
+        \caption{The state machine of exercise 9.6.}
+        \label{fig:9.6}
+    \end{figure*}
+
+    All is needed is to add a state $q_f$ in which we can loop forever for every undefined transition, except those of the final state(s).
 \end{solution}
 
diff --git a/exercises.icl b/exercises.icl
index f0f583c..0fe8f31 100644
--- a/exercises.icl
+++ b/exercises.icl
@@ -6,7 +6,7 @@ import TuringMachines
 Start :: *World -> *World
 Start w
 # (io,w)    = stdio w
-# m         = initTuringMachine ex_9_4 tape_9_4
+# m         = initTuringMachine ex_9_3_b tape_9_3_b
 # io        = fwrites (toString m +++ "\n") io
 # io        = loop m io
 # (ok,w)    = fclose io w
@@ -19,6 +19,20 @@ where
     | m.running == Running = loop m f
     | otherwise = f
 
+tape_9_2_b = [Just c \\ c <- fromString "abab"]
+ex_9_2_b :: TuringMachine Char
+ex_9_2_b = { alphabet = ['a', 'b'],
+             inputs = ['a', 'b'],
+             transition = f }
+where
+    f :: Int (Maybe Char) -> TuringMachineMove Char
+    f 0 Nothing     = Step 1 Nothing    Right
+    f 1 (Just 'c')  = Step 2 (Just 'c') Left
+    f 1 c           = Step 1 c          Right
+    f 2 (Just 'a')  = Step 2 (Just 'a') Left
+    f 2 (Just 'b')  = Step 2 (Just 'b') Left
+    f _ _           = Halt
+
 tape_9_3_b = [Just c \\ c <- fromString "abbaba"]
 ex_9_3_b :: TuringMachine Char
 ex_9_3_b = { alphabet = ['a', 'b', 'X', 'Y'],
@@ -117,3 +131,32 @@ where
 
     f _ _           = Halt
 
+tape_9_5_c = [Just c \\ c <- fromString "abbabbabaa"]
+ex_9_5_c :: TuringMachine Char
+ex_9_5_c = { alphabet = ['a', 'b'],
+             inputs = ['a', 'b'],
+             transition = f }
+where
+    f :: Int (Maybe Char) -> TuringMachineMove Char
+    f 0 Nothing     = Step 1 Nothing    Right
+
+    f 1 (Just 'a')  = Step 2 (Just 'X') Left
+    f 1 (Just c)    = Step 1 (Just c)   Right
+    f 1 Nothing     = Step 5 Nothing    Left
+
+    f 2 (Just 'b')  = Step 2 (Just 'b') Left
+    f 2 (Just 'X')  = Step 2 (Just 'X') Left
+    f 2 Nothing     = Step 3 Nothing    Right
+
+    f 3 (Just 'X')  = Step 3 (Just 'X') Right
+    f 3 (Just 'a')  = Step 3 (Just 'a') Right
+    f 3 (Just 'b')  = Step 4 (Just 'X') Right
+
+    f 4 (Just c)    = Step 4 (Just c)   Left
+    f 4 Nothing     = Step 1 Nothing    Right
+
+    f 5 (Just 'X')  = Step 5 (Just 'X') Left
+    f 5 Nothing     = Step 6 Nothing    Right
+
+    f _ _           = Halt
+
-- 
cgit v1.2.3