in Theory of Computation edited by
217 views
0 votes
0 votes

in Theory of Computation edited by
217 views

1 comment

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

1 Answer

2 votes
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.

selected by

Related questions