Additions: 9.3,9.4,9.5,9.6; CleanTuringMachines; fixes

5 files changed, 226 insertions, 35 deletions

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}
 
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}
 
diff --git a/ex9-5.tex b/ex9-5.tex
new file mode 100644
index 0000000..c3a56b7
--- /dev/null
+++ b/ex9-5.tex
@@ -0,0 +1,14 @@
+\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. 
+            
+            %todo draw machine
+
+        \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.
+
+            %todo draw machine
+    \end{enumerate}
+\end{solution}
+
diff --git a/ex9-6.tex b/ex9-6.tex
new file mode 100644
index 0000000..58f14d2
--- /dev/null
+++ b/ex9-6.tex
@@ -0,0 +1,4 @@
+\begin{solution}{6}
+    This is not much different from 5a. %todo
+\end{solution}
+
diff --git a/exercises.tex b/exercises.tex
index 5c3ecda..0b71584 100644
--- a/exercises.tex
+++ b/exercises.tex
@@ -2,6 +2,9 @@
 
 \usepackage[margin=2cm]{geometry}
 
+\PassOptionsToPackage{hyphens}{url}
+\usepackage[hidelinks]{hyperref}
+
 \usepackage{enumitem}
 \setenumerate[1]{label=\alph*)}
 
@@ -16,14 +19,28 @@
 \fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
 \pagestyle{fancy}
 
+% Solution environment
+\newenvironment{solution}[1]{\medskip\noindent{\textbf{Exercise \thesection.#1}\rm\par}{\medskip}}
+
+% Note command
+\usepackage[usenames,dvipsnames,svgnames]{xcolor}
+\newcommand{\note}[1]{%
+    \colorbox{AntiqueWhite}{\parbox[t]{\linewidth}{%
+        \vspace{.5\baselineskip}\setlength{\leftskip}{.5\baselineskip}\setlength{\rightskip}{\leftskip}%
+        #1\par%
+        \vspace{.5\baselineskip}\setlength{\leftskip}{0pt}\setlength{\rightskip}{0pt}%
+    }}%
+}
+
+\usepackage{minted}
+\definecolor{mintedbg}{rgb}{0.9,0.9,0.9}
+%Todo write a pygments lexer for Clean
+
 \usepackage{tikz}
 \usetikzlibrary{positioning,arrows,automata}
 
 \usepackage{amsmath}
 
-% Solution environment
-\newenvironment{solution}[1]{\medskip\noindent{\textbf{Exercise \thesection.#1}\rm\par}{\medskip}}
-
 \parindent0pt
 
 \title{Solutions to selected exercises from Thomas Sudkamp, \textit{Languages and Machines} (second edition)}
@@ -36,10 +53,16 @@
 
 \setcounter{section}{8}
 \section{Turing machines}
+
+\note{A Clean\footnotemark{} implementation of Turing machines may be found at \url{https://github.com/camilstaps/CleanTuringMachines} for testing purposes.}
+\footnotetext{\url{http://clean.cs.ru.nl}}
+
 \input{ex9-1.tex}
 \input{ex9-2.tex}
 \input{ex9-3.tex}
 \input{ex9-4.tex}
+\input{ex9-5.tex}
+\input{ex9-6.tex}
 
 \end{document}