2
$\begingroup$

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..

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – rus9384 Oct 19 '17 at 8:51
  • $\begingroup$ @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? $\endgroup$ – cnmesr Oct 19 '17 at 9:03
  • $\begingroup$ 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. $\endgroup$ – rus9384 Oct 19 '17 at 9:07
  • $\begingroup$ This is a special case of cs.stackexchange.com/questions/640/… $\endgroup$ – Gilles 'SO- stop being evil' Oct 19 '17 at 12:53
  • $\begingroup$ @Gilles Please check my edit $\endgroup$ – cnmesr Oct 19 '17 at 23:43
4
$\begingroup$

A decimal number is divisible by 4 if the number formed by its last two digits are divisible by 4. Stated differently, divisibility by 4 depends only on the last two digits. That should be enough for you to show that your language is regular.

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

$\endgroup$
  • $\begingroup$ Can you please check my Edit? I've used your explanation and the given link and had created it like that. But I don't know how to continue :s I hope the part I created is correct at least? $\endgroup$ – cnmesr Oct 19 '17 at 23:42
  • $\begingroup$ Unfortunately I cannot replace your TA. $\endgroup$ – Yuval Filmus Oct 20 '17 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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