Is my solution correct for problem 1.37 in Sipser's Theory of Computation?

449 Views Asked by At

The problem is as follows:

Let $ \Sigma_3=\left\{\begin{bmatrix}0\\0\\0\end{bmatrix},\begin{bmatrix}0\\0\\1\end{bmatrix},\begin{bmatrix}0\\1\\0\end{bmatrix},\ldots,\begin{bmatrix}1\\1\\1\end{bmatrix}\right\} $

So $\Sigma_3$ contains all size 3 columns of 0s and 1s. A string of symbols in $\Sigma_3$ give three rows of 0s and 1s. Consider each row to be a binary number, and let

$$B = \left\{ w \in (\Sigma_3)^* \mid \text{ the bottom row of } w \text{ is the sum of the top two rows} \right\}$$

So $\begin{bmatrix}0\\0\\1\end{bmatrix}\begin{bmatrix}1\\0\\0\end{bmatrix}\begin{bmatrix}1\\1\\0\end{bmatrix} \in B$, but $\begin{bmatrix}0\\0\\1\end{bmatrix}\begin{bmatrix}1\\0\\1\end{bmatrix} \notin B$

Show that $B$ is regular.

Now, there's a hint in there that tells us we can try showing that $B^R$ is regular, where $B^R$ is the reverse of $B$. (It is assumed that the reverse of a regular language is also regular, shown in a separate problem).

Now, here's my solution:

Let $a = \begin{bmatrix}1\\0\\1\end{bmatrix}, b = \begin{bmatrix}1\\1\\0\end{bmatrix}, c = \begin{bmatrix}0\\1\\1\end{bmatrix}, d = \begin{bmatrix}0\\0\\0\end{bmatrix}$

And then let

$e = \begin{bmatrix}1\\0\\0\end{bmatrix}, f = \begin{bmatrix}0\\1\\0\end{bmatrix}, g = \begin{bmatrix}1\\1\\1\end{bmatrix}, h = \begin{bmatrix}0\\0\\1\end{bmatrix}$

We'd get the following finite state machine recognizing $B^R$:

Finite state machine diagram

Basically, $q_2$ is the "carry" state, whereas $q_1$ is the final state as there is no carrying necessary.

Since we're solving this in a reverse fashion, i.e. solving for $B^R$, there are only four valid first choices out of 8 in total: $a$, $c$, and $d$, for which there is no carrying, and $b$ for which there is.

If we're in state $q_2$, which means we're carrying the 1, only $e$, $f$, $g$ and $h$ make sense. Out of those, only $h$ can send us to $q_1$, since there's nothing to carry.

I apologize if my English makes the above sounds awkward (especially the "carrying" part), but I hope the solution is understandable.