0
Design a DFA to check whether a given number is divisible by 4
finite automata • 15k  views
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

enter image description here

0
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more