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

Subject : Automata Theory

Topic : Finite Automata

Marks : 5M

0  upvotes
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  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More