blob: 5755dafc8f38eaa0f8ffa580e2bc15c1595a62e4 (
plain) (
blame)
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
|
\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}
|
