Consider the language $L$ with symbols that can be written from the alphabet $$ \Sigma = \left\{ \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} \right\} $$ such that, when concatenated, the second line is three times plus one the first line (in binary). I have to show that $L$ is regular by providing a $DFA$.
What I know: The technique is to think of $L^R$, the reverse language, provide it's $DFA$ and apply an algorithm (that I already know) and get to ${L^R}^R=L$.
What I don't understand: I found the $DFA$ that recognizes $L^R$,
,
but I don't understand it's functioning.
I appreciate any help, and thanks in advance.
The three nodes above represents the carry-over of current multiplication. $q_0$ particularly stands for the operation on the least significant bit since we have to plus 1 additionally. If the last digit is $[0,0]$, then we knows it cannot be right. Thus no transition from $q_0$ marked with $[0,0]$ can be found. If it is $[1, 0]$, then this digit is verified and the carry-over is $\displaystyle\frac{1*3+1}2=2$, which means that we will have to add an additional 2 when we check the next digit.
The other nodes perform alike. I shall leave it to you. The accepting state is that we have checked all the digits and the residual carry-over is $0$.
One more thing, $q_0$ can be replaced by the middle node above which is marked by $1$. Think about it if you successfully figure out why the current DFA works for $L^R$.