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

Improve this question
$\endgroup$
6
  • 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, 2017 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, 2017 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, 2017 at 9:07
  • $\begingroup$ This is a special case of cs.stackexchange.com/questions/640/… $\endgroup$
    – Gilles 'SO- stop being evil'
    Oct 19, 2017 at 12:53
  • $\begingroup$ @Gilles Please check my edit $\endgroup$
    – cnmesr
    Oct 19, 2017 at 23:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2017 at 23:42
  • $\begingroup$ Unfortunately I cannot replace your TA. $\endgroup$
    – Yuval Filmus
    Oct 20, 2017 at 0:07

Your Answer

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

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