Draw DFA that accepts concatenated binary string with condition

Question

Let $\Sigma = \{0,1\}$, with $w \in \Sigma^* $ and $value(w)$ the not negative integer value of $w$. $w$ is seen as binary string, with its first index being the least significant bit:

$$value(w_1 w_2 ... w_n) =  \Sigma_{i=i}^n 2^{i-1} w_i$$

The languages is defined as: $$L = \{a_1b_1a_2b_2 ... a_nb_n \ \in \ \Sigma^* \ \vert \ value(a_1a_2 ... a_n) = 3 \ \cdot \ value(b_1b_2 ... b_n)\}$$

The task is to draw the accepting DFA. I frankly have no idea on how to approach this question. Can someone give me a hint, not the full answer please?

Answer 1

Hint: $3\operatorname{value}(u)=\operatorname{value}(u)+\operatorname{value}(0u)$. Then you're just doing a simple addition with carry.

---

By the way, there's a much stronger result: For any first order formula $\varphi(x_1,\dots,x_n)$ of the Presburger arithmetic, there is an automaton $A$ over $\{0,1\}^n$ so that $A$ accepts $u$ iff $\varphi(\operatorname{value}_1(u),\dots,\operatorname{value}_n(u))$ is true (where $\operatorname{value}_i(u)$ is the same value that you defined except that since each "letter" of $\{0,1\}^n$ contains several digits, it only looks at the $i^{th}$).

Your question is a special case of this where the formula is $\varphi(a,b)= ``a=3b"$. (Kind of: if $L$ is what you get for this formula, then you'd need to take $f(L)$ where $f$ is the morphism defined by $(b_1,b_2)\mapsto b_1b_2$).