Question

Number of states in minimal finite automata that accepts all binary strings that starts with 101 and is divisible by 100.

A. 102

B. 103

C. 104

D. 105

Comments

How many states required for checking if a binary string is divisible by 4?

---

@habibkhan draw using http://madebyevan.com/fsm/, to visualize your FA. Use small MOD for simplicity. 

---

The number of states in minimal Dfa which accepts all string divisible by 100 should be 27 then why it is 100.

100/2 50/2  25+2=27 states in mDFA

Answer 1

I tried in the following way,

• first bulid the mod 100 structure.
• Then add the starting with '101' DFA and point it to state 5.

 

although I have not completed the MOD 100 machine !

Please verify someone !

Comments

Then in that case I think 104 states will required in DFA.

First we need to ensure string should start with 101 here we need 4 states (including trap state) and now we have to ensure length multiple of 100.So string start with 101 includes length 3 plus we now need 98 state to make sure  length should be 100.

Once we done with that .Now we need to make sure length multiple of 100.So we have to add 2 more state to make a loop of legth multiple of 100.So total 104 state will require.

In NFA 103 states  .

Qus about min FA so 103 states .

---

It's nice diagram to understand this type of question but I think it should be 98 states to accept rest of the 97 symboles of the required string which starting with 101. So total least no of states for NFA=103 and for DFA=104.

---

yes correct.

Answer 2

divisible by 100 means it is part of mod machine .so here no of states is 100 also the machine is starting with 101 so we need 4 more state .as it tell no of states in minimal nfa .so  include dead state during start od machine so 1 more state .

100+4+1=105

(d)option

Comments

how you are just adding both ?