From 76f9c0f6f3ce60b96a87d9a65688fa4b0808f99e Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Thu, 3 Sep 2015 22:52:39 +0200
Subject: Additions: 9.3,9.4,9.5,9.6; CleanTuringMachines; fixes

---
 ex9-4.tex | 36 +++++++++++++++++++++++++++++++++++-
 1 file changed, 35 insertions(+), 1 deletion(-)

(limited to 'ex9-4.tex')

diff --git a/ex9-4.tex b/ex9-4.tex
index 52267b9..8109d68 100644
--- a/ex9-4.tex
+++ b/ex9-4.tex
@@ -1,5 +1,5 @@
 \begin{solution}{4}
-    See figure \ref{fig:9.4}.
+    See figure \ref{fig:9.4} and \ref{fig:9.4-clean}.
 
     \begin{figure*}[p]
         \centering
@@ -25,5 +25,39 @@
         \caption{The state machine of exercise 9.4.}
         \label{fig:9.4}
     \end{figure*}
+
+    \begin{figure}[h]
+        \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{text}
+			tape_9_4 = [Just c \\ c <- fromString "baaabbaaacabab"]
+			ex_9_4 :: TuringMachine Char
+			ex_9_4 = { alphabet = ['a', 'b', 'c'],
+			           inputs = ['a', 'b', 'c'],
+			           transition = f }
+			where
+			    f :: Int (Maybe Char) -> TuringMachineMove Char
+			    f 0 Nothing     = Step 1 Nothing    Right
+			
+			    f 1 (Just 'a')  = Step 2 (Just 'a') Right
+			    f 1 c           = Step 1 c          Right
+			
+			    f 2 (Just 'a')  = Step 3 (Just 'a') Right
+			    f 2 c           = Step 1 c          Right
+			
+			    f 3 (Just 'a')  = Step 4 (Just 'a') Right
+			    f 3 c           = Step 1 c          Right
+			
+			    f 4 (Just 'a')  = Step 4 (Just 'a') Right
+			    f 4 (Just 'c')  = Step 5 (Just 'c') Left
+			    f 4 c           = Step 1 c          Right
+			
+			    f 5 (Just c)    = Step 5 (Just c)   Left
+			
+			    f _ _           = Halt
+        \end{minted}
+        \caption{The state machine of exercise 9.4, for use with CleanTuringMachines.}
+        \label{fig:9.4-clean}
+    \end{figure}
+
+    The intuition is that in state $q_i$ we have read $i-1$ consecutive $a$s, for $i\in\{1,2,3,4\}$, or even more in the case of $q_4$. Hence, the only possibility to let the machine terminate should be when we read a $c$ in $q_4$. This is done in $q_5$, which also has the function of bringing back the tape head to position $0$.
 \end{solution}
 
-- 
cgit v1.2.3

