Question: Design a DFA to check whether a given number is divisible by 4

0

0

We take sample numbers such as 4,8,16,32 in binary form, as we need a sequence of bits(here, 0’s and 1’s) not the entire number as it is.

4 => 100 (divisible)

8 => 1000 (divisible)

16 => 10000 (divisible)

32 => 100000 (divisible)

33 => 100001 (not divisible)

Hence, we observe that for numbers to be divisible by 4, the last two bits should be 0, because if both of them or either of them becomes 1, the sum of those two bits in decimal wouldn’t be divisible by 4

Eg:

011 => 3 (not divisible by 4)

010 =>2 (not divisible by 4)

001 => 1 (not divisible by 4)

Therefore, the input sequence must end with 00

DFA is

Please log in to add an answer.