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?


1 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$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.