From 8e91d1aac2268cc14046c16db1c42f601cc15202 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Mon, 31 Aug 2015 14:18:47 +0200
Subject: Ex 9.3bc; moving figures to separate float page

---
 ex9-1.tex     |  2 +-
 ex9-2.tex     |  2 +-
 ex9-3.tex     | 41 +++++++++++++++++++++++++++++++++++++++++
 ex9-4.tex     |  2 +-
 exercises.tex |  1 +
 5 files changed, 45 insertions(+), 3 deletions(-)
 create mode 100644 ex9-3.tex

diff --git a/ex9-1.tex b/ex9-1.tex
index c06f4f0..9c4786d 100644
--- a/ex9-1.tex
+++ b/ex9-1.tex
@@ -8,7 +8,7 @@
             \end{align*}
         \item See figure \ref{fig:9.1c}.
             
-            \begin{figure*}[t]
+            \begin{figure*}[p]
                 \centering
                 \begin{tikzpicture}[->, node distance=2cm]
 	                \node[state,initial] (q0) {$q_0$};
diff --git a/ex9-2.tex b/ex9-2.tex
index 5755daf..59dc012 100644
--- a/ex9-2.tex
+++ b/ex9-2.tex
@@ -8,7 +8,7 @@
             \end{align*}
         \item See figure \ref{fig:9.2c}.
             
-            \begin{figure*}[t]
+            \begin{figure*}[p]
                 \centering
                 \begin{tikzpicture}[->, node distance=2cm]
 	                \node[state,initial] (q0) {$q_0$};
diff --git a/ex9-3.tex b/ex9-3.tex
new file mode 100644
index 0000000..8a4b070
--- /dev/null
+++ b/ex9-3.tex
@@ -0,0 +1,41 @@
+\begin{solution}{2}
+    \begin{enumerate}
+        \setcounter{enumi}{1}
+        \item See figure \ref{fig:9.3b}.
+            
+            \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*}
+
+        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.
+            
+            %Todo draw a diagram
+    \end{enumerate}
+\end{solution}
+
diff --git a/ex9-4.tex b/ex9-4.tex
index 6c33eef..52267b9 100644
--- a/ex9-4.tex
+++ b/ex9-4.tex
@@ -1,7 +1,7 @@
 \begin{solution}{4}
     See figure \ref{fig:9.4}.
 
-    \begin{figure*}[t]
+    \begin{figure*}[p]
         \centering
         \begin{tikzpicture}[->, node distance=2cm]
             \node[state,initial] (q0) {$q_0$};
diff --git a/exercises.tex b/exercises.tex
index d53c468..f26fe6f 100644
--- a/exercises.tex
+++ b/exercises.tex
@@ -37,6 +37,7 @@
 \section{Turing machines}
 \input{ex9-1.tex}
 \input{ex9-2.tex}
+\input{ex9-3.tex}
 \input{ex9-4.tex}
 
 \end{document}
-- 
cgit v1.2.3