diff options
Diffstat (limited to 'ex9-2.tex')
| -rw-r--r-- | ex9-2.tex | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/ex9-2.tex b/ex9-2.tex new file mode 100644 index 0000000..5755daf --- /dev/null +++ b/ex9-2.tex @@ -0,0 +1,28 @@ +\begin{solution}{2} + \begin{enumerate} + \item \begin{align*} + & q_0BabcabB \vdash Bq_1abcabB \\\vdash& Baq_1bcabB \vdash Babq_1cabB \\\vdash& Baq_2bcabB \vdash Bq_2aacabB \\\vdash& q_2BbacabB. + \end{align*} + \item \begin{align*} + & q_0BababB \vdash Bq_1ababB \\\vdash& Baq_1babB \vdash Babq_1abB \\\vdash& Babaq_1bB \vdash Bababq_1B \\\vdash& BababBq_1B \dots + \end{align*} + \item See figure \ref{fig:9.2c}. + + \begin{figure*}[t] + \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$}; + \draw (q0) -- node[above] {$B/B,R$} ++ (q1); + \draw (q1) edge[loop above] node[above,align=left] {$b/b,R$\\$a/a,R$\\$B/B,R$} (q1); + \draw (q1) -- node[above] {$c/c,L$} ++ (q2); + \draw (q2) edge[loop above] node[above,align=left] {$b/a,L$\\$a/b,L$} (q2); + \end{tikzpicture} + \caption{The state machine of exercise 9.2c.} + \label{fig:9.2c} + \end{figure*} + \item Replace all $a$s with $b$s and vice versa on the left of the first $c$, if it exists. If it does not exist, the string is not modified but the machine never terminates. + \end{enumerate} +\end{solution} + |