diff options
| -rw-r--r-- | ex9-3.tex | 178 | ||||
| -rw-r--r-- | ex9-4.tex | 36 | ||||
| -rw-r--r-- | ex9-5.tex | 14 | ||||
| -rw-r--r-- | ex9-6.tex | 4 | ||||
| -rw-r--r-- | exercises.tex | 29 |
5 files changed, 226 insertions, 35 deletions
@@ -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} @@ -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} |