How to create a DFA that accepts strings that are multiples of a number?

Question

I particularly have a problem creating DFAs for multiples of larger numbers like 10, 11 ,12 etc. but I can create simple ones like 1, 2, 3 etc.

Even more so, I have a problem creating a minimized DFA for these problems. I think if a DFA has 10, 11 or so states, minimizing it properly could take a long time as there can be approx. pow(2,10) transitions. I am particularly having problem with the following:

Minimum number of states in a deterministic finite automata that accepts the strings over the alphabet {0,1} beginning with a 1 and which, if interpreted as a binary number, is a multiple of 10.

This language has the strings = {0, 1010, 10100, 11110, ....} and there doesn't seem to be any pattern that is followed. Is there any universal approach that works for creating such counting DFAs and minimizing them?

Answer 1

Instead of finding a pattern in their binary representation, observe how their remainder changes. A multiple of N would give a remainder 0 when divided by N, or equivalently 0 when you apply mod N operation.

For example, If want to check if 5 is a multiple of 0 or not, start with its binary representation, and assuming you are reading from MSB to LSB, the machine would encounter the first bit of 101 i.e. 1. At this point, your machine knows it has a 1 as input and 1mod10 is 1, so it will have a remainder state 1. Similarly, you will have a state for each remainder from 0-9. Now when it reads 0, the machine has an input 2 (10 in binary==2). So now you have to find out from the remainder state of 1, upon encountering a 0, what is the remainder state now. Do this for all states and you will have your DFA constructed. Remainder state 0 would be the accepting state.