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

BUT THE ANS IS 7 STATES

---

Please get it confirmed from where u took the test and please let me know if my solution is wrong. :)

---

@tusharp

your explaination need some correction read the below comment

A minimal DFA which accepts strings divisible by 5 contains 5 states. (assume name of this DFA is DFA G for the further explanation )

now we make a new  initial state 

now this initial state will have to transition transition 1  to the initial state of the of DFA G

and new initial state  have transition 0 to the dead state 

so total state is 7

---

Yes I missed dead state 

@Gurdeep Saini answer edited :)

Thank you 

---

@tusharp

@Gurdeep Saini question is asking about minimal FA, not minimal DFA...

I think we can go with NFA...which requires 6 states??

---

 minimal finite automata means minimal DFA

@himgta

did you learnt about minimal NFA

---

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 !