Show that $L$ is regular, given $L = \{w \in \sum^*|$ the last column in $w$ is twice the first column $\}$

Question

Additional information: $\sum = \{[0 0], [0 1],[1 0], [1 1] \}, \sum$ contains all rows of $0$'s and $1$'s of size 2. Consider each column to be a binary number prove that $L = \{w \in \sum^*|$ the last column in $w$ is twice the first column $\}$

For example $[0 0] [0 1] [1 0] [0 0] \in L$ (because the first columns form the number $0010 = 2$ and the second columns form the binary number $0100 = 4$) and $[0 0] [0 1] [1 0] [0 1] \in L$ (because the first columns form $0010 = 2$ and the second columns form $0101 = 5$). Show that $L$ is regular.

I'm thinking the easiest way to do this is to construct a regular expression. I've conjectured that to make any binary number twice as big you have to concatenate with a $0$ on the right, essentially multiplying the original string by 2.

That being said I know I need to create two strings with any combinations of $0$'s and $1$'s $(0 + 1)^*$ but these two strings need to be identical and at the end just concatenate the $0$. The trouble I'm having is creating the identical strings of any combinations of $0$'s and $1$'s. Is this even possible using a regular expression? Is there perhaps a simpler approach?

Answer 1

This DFA accepts your language. As you stated, the second column must the the first, bitshifted by one. On the other hand that means, whatever character we read currently for the second column, it must be the same character in the first column of the next pair.

First, $q_0$ is just our starting state that removes all leading zeroes. As the second column must be twice the first, the binary number represented by the second column has one more digit than the first, so after some number of $00$ we must have $01$. Now all the other two states say is this:

• $q_1$: The last character of the second column was 1. The next character in the first column therefore must be 1.
• $q_2$: analogous for 0.

Note that they do exactly that. All incoming transitions for $q_1$ have a 1 in the second column and all outgoing transitions have a 1 in the first column. Same with 0 for $q_w$. Finally, only $q_2$ is a final state, because we know the second column must represent an even number and therefore end on a 0.

I found this easier than searching for the regex, but you can just derive that from the DFA and see whether it might have some intuitive meaning.