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?
Draw DFA that accepts concatenated binary string with condition
regular languages;finite automata
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$).