diff options
Diffstat (limited to 'ex9-5.tex')
| -rw-r--r-- | ex9-5.tex | 93 |
1 files changed, 89 insertions, 4 deletions
@@ -1,14 +1,99 @@ \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. + \item See figure \ref{fig:9.5a}. + + \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=of q1] {$q_4$}; + \node[state,accepting] (q5) [right=of q4] {$q_5$}; + \draw (q0) -- node[above] {$B/B,R$} ++ (q1); + \draw (q1) -- node[above] {$a/X,R$} ++ (q2); + \draw (q2) edge[loop above] node[above,align=left] {$a/a,R$\\$Y/Y,R$} (q2); + \draw (q2) -- node[above] {$b/Y,L$} ++ (q3); + \draw (q3) edge[loop right] node[right,align=left] {$a/a,L$\\$Y/Y,L$} (q3); + \draw (q3) edge[bend right, out=300, in=240, looseness=1.3] node[above] {$X/X,R$} (q1); + \draw (q1) -- node[left,align=right] {$B/B,R$\\$Y/Y,R$} ++ (q4); + \draw (q4) edge[loop left] node[left] {$b/b,R$} (q4); + \draw (q4) -- node[above] {$B/B,R$} ++ (q5); + \end{tikzpicture} + \caption{The state machine of exercise 9.5a.} + \label{fig:9.5a} + \end{figure*} - %todo draw machine + The intuition is: 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. \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. + \item See figure \ref{fig:9.5c} and \ref{fig:9.5c-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) [right=of q3] {$q_4$}; + \node[state] (q5) [below=of q1] {$q_5$}; + \node[state,accepting] (q6) [right=of q5] {$q_6$}; + \draw (q0) -- node[above] {$B/B,R$} ++ (q1); + \draw (q1) edge[loop above] node[above,align=left] {$b/b,R$\\$X/X,R$} (q1); + \draw (q1) -- node[above] {$a/X,L$} ++ (q2); + \draw (q2) edge[loop above] node[above,align=left] {$b/b,L$\\$X/X,L$} (q2); + \draw (q2) -- node[above] {$B/B,R$} ++ (q3); + \draw (q3) edge[loop above] node[above,align=left] {$a/a,R$\\$X/X,R$} (q3); + \draw (q3) -- node[above] {$b/X,R$} ++ (q4); + \draw (q4) edge[loop right] node[right,align=left] {$a/a,L$\\$b/b,L$\\$X/X,L$} (q4); + \draw (q4) edge[bend right, out=300, in=240, looseness=1.2] node[above] {$B/B,R$} (q1); + \draw (q1) -- node[left] {$B/B,L$} ++ (q5); + \draw (q5) edge[loop left] node[left] {$X/X,L$} (q5); + \draw (q5) -- node[above] {$B/B,R$} ++ (q6); + \end{tikzpicture} + \caption{The state machine of exercise 9.5c.} + \label{fig:9.5c} + \end{figure*} - %todo draw machine + \begin{figure}[h] + \begin{minted}[bgcolor=mintedbg,tabsize=0,fontsize=\footnotesize]{text} + tape_9_5_c = [Just c \\ c <- fromString "abbabbabaa"] + ex_9_5_c :: TuringMachine Char + ex_9_5_c = { alphabet = ['a', 'b'], + inputs = ['a', 'b'], + transition = f } + where + f :: Int (Maybe Char) -> TuringMachineMove Char + f 0 Nothing = Step 1 Nothing Right + + f 1 (Just 'a') = Step 2 (Just 'X') Left + f 1 (Just c) = Step 1 (Just c) Right + f 1 Nothing = Step 5 Nothing Left + + f 2 (Just 'b') = Step 2 (Just 'b') Left + f 2 (Just 'X') = Step 2 (Just 'X') Left + f 2 Nothing = Step 3 Nothing Right + + f 3 (Just 'X') = Step 3 (Just 'X') Right + f 3 (Just 'a') = Step 3 (Just 'a') Right + f 3 (Just 'b') = Step 4 (Just 'X') Right + + f 4 (Just c) = Step 4 (Just c) Left + f 4 Nothing = Step 1 Nothing Right + + f 5 (Just 'X') = Step 5 (Just 'X') Left + f 5 Nothing = Step 6 Nothing Right + + f _ _ = Halt + \end{minted} + \caption{The state machine of exercise 9.5c, for use with CleanTuringMachines.} + \label{fig:9.5c-clean} + \end{figure} + + The intuition is: 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. \end{enumerate} \end{solution} |