1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
\begin{solution}{3}
\begin{enumerate}
\setcounter{enumi}{1}
\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}[h]
\begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{clean}
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 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]{clean}
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.
\end{enumerate}
\end{solution}
|
