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

is it 104 ?

---

ya 104 but how?

---

Ans is 103 or 104?? I m getting confused. Plz explain properly...

---

What is the answer??I suppose it should be 102 since we are asked about MFA meaning minimal finite automata and by default finite automata is assumed as NFA not DFA since NFA is more convenient than DFA from ease of design point of view.

---

NFA will accept in 102 and DFA in 103 ...MFA means NFA (we always consider NFA in case of only finite automa said)here

---

Provided ans is 104 by ACE. I m not getting a proper explaination by them.

---

Assuming NFA, why we need 102 states?

---

One trap state to deal with "begin with" condition and hence we cannot make initial state as final state as we normally do in mod machines but what can we do is we can first accept an string of length 100 by having 101 states(in normal mod machine 100 state would do but due to "begin" condtion) , making the last state q₁₀₀ as final state and on further receiving input either a or b , we feedback to the second state from the beginning i.e. q₁ so as to ensure we keep on getting loops of 100 only.Further we connect q_{0 ,} q₁ and q₂ to trap state say q₁₀₁ to handle the begin condition.

So in total 102 states for NFA should be correct in my opinion.

---

@Arjun Sir verify this .The same qus is answered here.

https://gateoverflow.in/70749/number-of-states-in-minimal-finite-automata?show=70820#c70820

---

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 ?