# How do you prove that the set of decimal representation of the 4 divisble natural numbers is regular?

This is from an old exam, the last Task no one could solve correctly and I'm curious how it's done :p

Show that the set of decimal representation (without leading zeroes) of the divisible numbers by 4 (natural numbers) is regular.

By this thread How to prove a language is regular? I know that one can make a DFA to Show that a language is regular.

But is that possible at all because we have infinite natural numbers that are divisible by 4..

I cannot even imagine how that DFA would look like :o

Maybe there is another way of showing this, too?

Edit: Removed..

• First answer how would a number divisible by 4 look like in binary. Hint: assuming that first input bit is LSB, the minimal DFA has only 3 states. Oct 19 '17 at 8:51
• @rus9384 I think I understand your hint but will Need 4 states. Could you check it if I edit my question in about 20 minutes? Oct 19 '17 at 9:03
• Well, if there are 4 states, it's not minimal (even if first bit is MSB). Accepting state can have transitions to non-accepting states. Oct 19 '17 at 9:07
• This is a special case of cs.stackexchange.com/questions/640/… Oct 19 '17 at 12:53
• @Gilles Please check my edit Oct 19 '17 at 23:43

The language of numbers in base $b$ divisible by $m$ is regular for all $b,m$, but that's somewhat harder to show.