Noob here with simple question. I'm building a DFA for a homework problem. I have to make a DFA where the binary representation of a number is divisble by N.
As a sample input of 5, I'm not sure if I need to use 101 or 00000101? Because that changes the state diagram based on which base I use.
On
Here are some suggestions, this is not an answer, but too long for a comment:
Suppose the input is in binary, LSB first. Presumably $N$ is a known, fixed number.
Compute $2^n \text{ mod } N$, this will generate a repeating sequence of length $\le N$, say $a_0,a_1,...,a_p$.
The idea is that we want to compute the number modulo $N$, so we need to know what our current result is and so our state needs to track the current value modulo $N$. It is essentially a counter.
As each bit comes in, it doubles the amount we need to 'advance'. However, since $p$ (from the above sequence) is finite, we can track this easily with another part of the state.
This suggests that a reasonable state is $(i,j)$ where $i \in \{0,...,N-1\}$ is the current number, and $j$ is the index of the $a_j$ above (so $j \in \{0,...,p\}$).
The initial state will be $(0,0)$, and in general, if the current state is $(i,j)$ and the input is $u \in \{0,1\}$, the next state will be $((i+a_j \cdot u ) \text{ mod } N, (j+1) \text{ mod (p+1)} ) $.
The current state will be accepting if it is of the form $(0,*)$.
I am not sure to understand your problem in the case $N = 5$. If I am not wrong, the automaton below accepts exactly the binary representations of a number divisible by $5$, including those leading with an arbitrary number of zeros, like $101, 0101, 00101, 000101$, etc.
$\hskip 100pt$