Let $\sum_3$ contains all size-3 columns of 0s and 1s as follows $$\sum_{3}= \begin{bmatrix}0 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix}0 \\ 0 \\ 1 \end{bmatrix}, \begin{bmatrix}0 \\ 1 \\ 0 \end{bmatrix},.., \begin{bmatrix}1 \\ 1 \\ 1 \end{bmatrix}$$
A string in Σ3 gives three rows of 0s and 1s. Consider each row to be a binary number. Let
$B = \{ω ∈ Σ_∗^3|$ the bottom row of ω is the sum of the top two rows}
For example,
$\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
This problem is marked as challenging in the book. It suggests that I work on $B^R$ first and then show B is regular. I am allowed to use the following theorem
Theorem: If $B$ is regular then $B^R$ is regular
$B^R$ is just all the strings reversed in B
How would you approach this problem?. I don't know why $B^R$ would help because given the language, it looks like there is no $B^R$ or $B^R=B$
Think of your language $B$ as the language of all valid binary long additions. Now you need to define an NFA that verifies whether a long addition is correct. As you perform long addition from the least significant bit first, this is easier to do for $B^R$.
You will need to keep track of a carry bit using two different states, starting in the no-carry state. Then, being in one of those two states, some inputs are valid, some are invalid, and some change the carry. For example $\begin{bmatrix}0\ 0\ 1\end{bmatrix}^T$ is valid in the carry state and doesn't produce a carry, whereas it's invalid in the non-carry state; $\begin{bmatrix}1\ 1\ 0\end{bmatrix}^T$ is valid if there's no carry, but it produces a carry.
You accept a string if you're left without a carry after reading it in completely.