retagged by
4,506 views
3 votes
3 votes

Q

no. of states in minimal DFA built for:

accepts all strings over the alphabet {0,1} interpreted as a binary number is congruent to zero modulo n has

a)n states

b)n-1 states

c)n+1 states

d)None of the above

basically, i didn't get what they are trying to say in this question?(correct answer is option A)

retagged by

2 Answers

Best answer
8 votes
8 votes
States in Modulo n are {0,1,2,3,........ upto n-1}

Total number of states are n ..
selected by
2 votes
2 votes

If we consider |W| as set of all strings over {0,1} then the condition that should be followed is |w| =0 mod n ac to question.

Here we are considering binary no .So in case of binary no if we divide any no with base of number which is 2 in case of binary then max remainder we can  are  either 0 or 1  (if we generalize it like if base is n then no of state we should consider is n-1)

if we take it up to n then max remainder we can get is {0 ,1 ,2 ,......n-i } which is n.

This is the reason we got n states here.

Related questions

1 votes
1 votes
1 answer
3
kislaya Pant asked May 8, 2018
1,066 views
Ques:- What are the number of final states in minimal DFA, where ∑= {a, b}, if every string starts with “aa” and length of the string is not congruent to 0 (mod 4)....
3 votes
3 votes
1 answer
4