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

Subject : Automata Theory

Topic : Finite Automata

Marks : 5M

ADD COMMENTlink
modified 10 months ago by gravatar for Abhishek Tiwari Abhishek Tiwari ♦♦ 50 written 3.3 years ago by gravatar for pratikj2208 pratikj22080
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

ADD COMMENTlink
written 3.3 years ago by gravatar for pratikj2208 pratikj22080
Please log in to add an answer.