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-3.tex | 178 +++++++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 147 insertions(+), 31 deletions(-)

(limited to 'ex9-3.tex')

diff --git a/ex9-3.tex b/ex9-3.tex
index 8a4b070..d849919 100644
--- a/ex9-3.tex
+++ b/ex9-3.tex
@@ -1,41 +1,157 @@
-\begin{solution}{2}
+\begin{solution}{3}
     \begin{enumerate}
         \setcounter{enumi}{1}
-        \item See figure \ref{fig:9.3b}.
+        \item See figure \ref{fig:9.3b} and \ref{fig:9.3b-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) [below right=of q2] {$q_4$};
-	                \node[state] (q5) [right=of q3] {$q_5$};
-                    \node[state] (q6) [above right=of q2] {$q_6$};
-                    \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
-                    \draw (q1) edge[loop above] node[above,align=left] {$a/a,R$\\$b/b,R$} (q1);
-                    \draw (q1) -- node[above,align=left] {$B/B,L$\\$X/X,L$\\$Y/Y,L$} ++ (q2);
-                    \draw (q2) -- node[above] {$a/X,R$} (q3);
-                    \draw (q2) -- node[below left] {$b/Y,R$} (q4);
-                    \draw (q3) edge[out=30,in=60,looseness=8] node[above,align=left] {$a/a,R$\\$b/b,R$\\$X/X,R$\\$Y/Y,R$} (q3);
-                    \draw (q3) -- node[above] {$B/a,L$} ++ (q5);
-                    \draw (q4) edge[loop below] node[below,align=left] {$a/a,R$\\$b/b,R$\\$X/X,R$\\$Y/Y,R$} (q4);
-                    \draw (q4) -- node[below right] {$B/b,L$} ++ (q5);
-                    \draw (q5) edge[loop above] node[above,align=left] {$a/a,L$\\$b/b,L$\\$X/X,L$\\$Y/Y,L$} (q5);
-                    \draw (q5) edge[out=270,in=270,looseness=2] node[below] {$B/B,R$} (q1);
-                    \draw (q2) -- node[above left] {$B/B,R$} ++ (q6);
-                    \draw (q6) edge[loop above] node[above,align=left] {$X/a,R$\\$Y/b,R$\\$a/a,L$\\$b/b,L$} (q6);
-                \end{tikzpicture}
-                \caption{The state machine of exercise 9.3b.}
-                \label{fig:9.3b}
-            \end{figure*}
+        \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 right=of q2] {$q_4$};
+                \node[state] (q5) [right=of q3] {$q_5$};
+                \node[state] (q6) [above right=of q2] {$q_6$};
+                \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
+                \draw (q1) edge[loop above] node[above,align=left] {$a/a,R$\\$b/b,R$} (q1);
+                \draw (q1) -- node[above,align=left] {$B/B,L$\\$X/X,L$\\$Y/Y,L$} ++ (q2);
+                \draw (q2) -- node[above] {$a/X,R$} (q3);
+                \draw (q2) -- node[below left] {$b/Y,R$} (q4);
+                \draw (q3) edge[out=30,in=60,looseness=8] node[above,align=left] {$a/a,R$\\$b/b,R$\\$X/X,R$\\$Y/Y,R$} (q3);
+                \draw (q3) -- node[above] {$B/a,L$} ++ (q5);
+                \draw (q4) edge[loop below] node[below,align=left] {$a/a,R$\\$b/b,R$\\$X/X,R$\\$Y/Y,R$} (q4);
+                \draw (q4) -- node[below right] {$B/b,L$} ++ (q5);
+                \draw (q5) edge[loop above] node[above,align=left] {$a/a,L$\\$b/b,L$\\$X/X,L$\\$Y/Y,L$} (q5);
+                \draw (q5) edge[out=270,in=270,looseness=2] node[below] {$B/B,R$} (q1);
+                \draw (q2) -- node[above left] {$B/B,R$} ++ (q6);
+                \draw (q6) edge[loop above] node[above,align=left] {$X/a,R$\\$Y/b,R$\\$a/a,L$\\$b/b,L$} (q6);
+            \end{tikzpicture}
+            \caption{The state machine of exercise 9.3b.}
+            \label{fig:9.3b}
+        \end{figure*}
+
+        \begin{figure}[h]
+            \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{text}
+				tape_9_3_b = [Just c \\ c <- fromString "abbaba"]
+				ex_9_3_b :: TuringMachine Char
+				ex_9_3_b = { alphabet = ['a', 'b', 'X', 'Y'],
+				             inputs = ['a', 'b'],
+				             transition = f }
+				where
+				    f :: Int (Maybe Char) -> TuringMachineMove Char
+				    f 0 Nothing     = Step 1 Nothing    Right
+
+				    f 1 (Just 'a')  = Step 1 (Just 'a') Right
+				    f 1 (Just 'b')  = Step 1 (Just 'b') Right
+				    f 1 c           = Step 2 c          Left
+
+				    f 2 Nothing     = Step 6 Nothing    Right
+				    f 2 (Just 'a')  = Step 3 (Just 'X') Right
+				    f 2 (Just 'b')  = Step 4 (Just 'Y') Right
+
+				    f 3 (Just c)    = Step 3 (Just c)   Right
+				    f 3 Nothing     = Step 5 (Just 'a') Left
+
+				    f 4 (Just c)    = Step 4 (Just c)   Right
+				    f 4 Nothing     = Step 5 (Just 'b') Left
+
+				    f 5 (Just c)    = Step 5 (Just c)   Left
+				    f 5 Nothing     = Step 1 Nothing    Right
+
+				    f 6 (Just 'X')  = Step 6 (Just 'a') Right
+				    f 6 (Just 'Y')  = Step 6 (Just 'b') Right
+				    f 6 (Just c)    = Step 6 (Just c)   Left
+
+				    f _ _           = Halt
+            \end{minted}
+            \caption{The state machine of exercise 9.3b, for use with CleanTuringMachines.}
+            \label{fig:9.3b-clean}
+        \end{figure}
 
         We read $a$s and $b$s from the input string until the end in $q_1$. The last character is replaced by an $X$ or $Y$ for an $a$ or $b$, respectively, by $q_2$. Then, we place an $a$ or $b$ on the first blank on the right, depending on the last character of the input string. This happens in $q_3$ and $q_4$. We go back to the very beginning of the string in $q_5$, and repeat the process starting in $q_2$, but now stop reading at the beforelast character (and the one before that, and so on). If there are no more characters in the input string, we go to $q_6$ where we replace all $X$s by $a$s and all $Y$s by $b$s, after which we terminate.
 
-        \item The idea would be to first move the last character to the right, then the last $2$ characters of the new string, then the last $3$ characters of that string, et cetera., until we are back at the leftmost position. This could be recognised by putting a marker there, if needed.
+    \item See figure \ref{fig:9.3c} and \ref{fig:9.3c-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) [above=of q2] {$q_3$};
+                \node[state] (q4) [right=of q2] {$q_4$};
+                \node[state] (q5) [below=2.5cm of q2] {$q_5$};
+                \node[state] (q6) [right=of q5] {$q_6$};
+                \node[state] (q7) [right=of q6] {$q_7$};
+                \node[state] (q8) [right=of q7] {$q_8$};
+
+                \draw (q0) -- node[above] {$B/B,R$} ++ (q1);
+                \draw (q1) edge[loop above] node[above,align=left] {$a/a,R$\\$b/b,R$} (q1);
+                \draw (q1) -- node[above,align=left] {$X/X,L$\\$B/X,L$} ++ (q2);
+                \draw (q2) edge[bend left] node[above left] {$a/X,R$} (q3);
+                \draw (q3) edge[bend left] node[above right,align=left] {$B/a,R$\\$X/a,R$} (q2);
+                \draw (q2) edge[bend left] node[above] {$b/X,R$} (q4);
+                \draw (q4) edge[bend left] node[below,align=left] {$B/b,R$\\$X/b,R$} (q2);
+                \draw (q2) -- node[left] {$B/B,L$} (q5);
+                \draw (q5) edge[bend left] node[above,align=left] {$a/a,L$\\$b/b,L$} (q6);
+                \draw (q6) edge[bend left] node[below] {$X/X,L$} (q5);
+                \draw (q6) -- node[above] {$B/B,R$} (q7);
+                \draw (q7) edge[loop above] node[above,align=left] {$a/a,R$\\$b/b,R$\\$X/X,R$} (q7);
+                \draw (q7) -- node[above] {$B/B,L$} (q8);
+                \draw (q8) edge[loop above] node[above,align=left] {$a/a,L$\\$b/b,L$\\$X/B,L$} (q8);
+            \end{tikzpicture}
+            \caption{The state machine of exercise 9.3c.}
+            \label{fig:9.3c}
+        \end{figure*}
+
+        \begin{figure}[h]
+            \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{text}
+				ex_9_3_c :: TuringMachine Char
+				ex_9_3_c = { alphabet = ['a', 'b', 'X'],
+				             inputs = ['a', 'b'],
+				             transition = f }
+				where
+				    f :: Int (Maybe Char) -> TuringMachineMove Char
+				    f 0 Nothing     = Step 1 Nothing    Right
+				
+				    f 1 (Just 'a')  = Step 1 (Just 'a') Right
+				    f 1 (Just 'b')  = Step 1 (Just 'b') Right
+				    f 1 (Just 'X')  = Step 2 (Just 'X') Left
+				    f 1 Nothing     = Step 2 (Just 'X') Left
+				
+				    f 2 (Just 'a')  = Step 3 (Just 'X') Right
+				    f 2 (Just 'b')  = Step 4 (Just 'X') Right
+				    f 2 Nothing     = Step 5 Nothing    Left
+				
+				    f 3 (Just 'X')  = Step 2 (Just 'a') Right
+				    f 3 Nothing     = Step 2 (Just 'a') Right
+				
+				    f 4 (Just 'X')  = Step 2 (Just 'b') Right
+				    f 4 Nothing     = Step 2 (Just 'b') Right
+				
+				    f 5 (Just 'a')  = Step 6 (Just 'a') Left
+				    f 5 (Just 'b')  = Step 6 (Just 'b') Left
+				
+				    f 6 (Just 'X')  = Step 5 (Just 'X') Left
+				    f 6 (Just 'a')  = Step 2 (Just 'a') Right
+				    f 6 (Just 'b')  = Step 2 (Just 'b') Right
+				    f 6 Nothing     = Step 7 Nothing    Right
+				
+				    f 7 (Just c)    = Step 7 (Just c)   Right
+				    f 7 Nothing     = Step 8 Nothing    Left
+				
+				    f 8 (Just 'X')  = Step 8 Nothing    Left
+				    f 8 (Just c)    = Step 8 (Just c)   Left
+				
+				    f _ _           = Halt
+            \end{minted}
+            \caption{The state machine of exercise 9.3c, for use with CleanTuringMachines.}
+            \label{fig:9.3c-clean}
+        \end{figure}
+        
+        The idea would be to first move the last character to the right, then the last $2$ characters of the new string, then the last $3$ characters of that string, et cetera., until we are back at the leftmost position. This could be recognised by putting a marker there, if needed.
             
-            %Todo draw a diagram
     \end{enumerate}
 \end{solution}
 
-- 
cgit v1.2.3

