Proving a language to be regular

Question

Let $\Sigma_{2}={ \begin{bmatrix} 0\\ 0 \end{bmatrix}, \begin{bmatrix} 1\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 1 \end{bmatrix},\begin{bmatrix} 1\\ 1 \end{bmatrix}}$

Here $\Sigma_{2}$ contains all columns of $0$ and $1$s of height $2$. A string of symbols in $\Sigma_{2}$ gives two rows of 0s and 1s. Consider each row to be a binary number and let:

$$C=\{w\in \Sigma^*_2 \mid\text{ the bottom row of }w\text{ is }3\text{ times the top row}\}\;.$$

For example: ${ \begin{bmatrix} 0\\ 0 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix}\begin{bmatrix} 1\\ 1 \end{bmatrix}\begin{bmatrix} 0\\ 0 \end{bmatrix}\in C}$ but ${ \begin{bmatrix} 0\\ 1 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix}\begin{bmatrix} 1\\ 0 \end{bmatrix}\notin C}$

Show that $C$ is regular.

I would like to get some tips on how to approach this problem, as I am new to learning about formal language theory.

Answer 1

Hint 1: If $\mathcal L$ is a regular language, then $\mathcal L^R = \{ w^R : w\in \mathcal L \}$ is also regular. ($w^R$ is the reverse of the string $w$.)

Hint 2:

The machine can go right to left on the input, checking that the multiplication is done correctly, storing only the carry bit from the previous input.

Answer 2

It’s easiest, I think, to use the fact that a language is regular if and only if its reversal is regular. (This pretty easy to prove using either regular grammars or DFAs, if you’ve not already seen it.) I’d construct a DFA that recognizes $C^R$, the reversal of $C$. In effect this amounts to thinking about a DFA that scans words backwards. I claim that if you scan a word $s\in\Sigma_2^*$ from right to left, it’s easy to tell whether it’s in $C$.

In order to be in $C$, $w$ can terminate in any number of $0\brack 0$s. Now $3\cdot1=3=11_{\text{two}}$, so when you finally encounter a $1$ in the top line, you must have a $1$ below it, and the multiplication also has a carry to the next column over. Thus, you need a $1\brack 1$, and you know that the multiplication of the top line by $3$ has a carry into the next column over. Continue in this fashion: as each symbol comes in, you need only its top symbol and the knowledge of whether there was a carry from the next column over in order to tell whether its bottom symbol is the right one. Use the states of the DFA to keep track of whether you have an incoming carry.