Ace book

Question

The minimal finite automata accepting the set of all strings over {0,1} starting with a 1 that interpreted as the binary representation of an integer are congruent to 0 modulo 5 has ______ states.

The ans is 7 but according to me modulo n has 5 states .?

Answer 1

Binary number interpreted as integer and you want  0 modulo 5, then we need 5 states. But as question is saying starting from 1, we add a new state which on input 1 will point to remainder 0 state of our mod 5 dfa and on 0 will go to dead state. So total 7 states.(5 states for mod 5 counting and 2 more for handling starting with 1 condition. )

Comments

i they say minimum no of state in finite automata  then it will be 6

---

Yes if they say minimum and only FA, then it is NFA

---

check arvin's discussion https://gateoverflow.in/229504/%23test-series

even most of the people saying, Minimal Fa means takes NFA by default

i don't know which one is correct !