I think 4 states are sufficient. Which makes A) option correct.

Dark Mode

217 views

2 votes

Best answer

If we make a DFA accepting binary strings divisible by 4 then it takes 4 states such as

state 0 : remainder 0 accepting 4,**8**,12,**16**,20,**24**,28,**32**,36,**40**...

state 1: remainder 1 accepting 1,5,9,13,17...

state 2: reaminder 2 accepting 2,6,10,14,18...

state 3: remainder 3 accepting 3,7,11,15,19....

This DFA is also accepting all stings divisible by 8 also..Thus

GCD (4,8) = 4

Even this is a pattern for every question like this for any other number such as divisible by 3,6 will take GCD (3,6) states.