670 views
1 votes
1 votes

3 Answers

1 votes
1 votes

should'nt we get 103 states without trap state.

101 --> used to identify 100 len string but we can't simply do transition on first two states on their next state as we also need to identify the first 3 letters.

say q--> q1 [on 1] and q1 --> q2 [on 0] and q2 --> q3 [on 1] then after normal on 0,1 to next state like qthen q5... and so on to q101 as final state...but now what if 101th digit comes can we go back to q0 .. answer is no.. so we make another state q'and q101 --> q'1 [on 0,1 and this is 101th char] then q'--> q'[on 0,1 and this is 102nd char] and q'--> q3 [as after that is normal mod machine states..to q101]

so we need 101 + 2 more --> 103 states without trap state.

0 votes
0 votes

take example of string "101" simply  to accept it we need 4 states  .

so now coming to question  to accept 100 length  string we need 101 states plus 1 state as dead state (because it should start only with 101 so we need 1 trap state here) so totally we need 102 states .!

so A) option answer .

–1 votes
–1 votes

Answer should be 104 states.

edited by

Related questions

0 votes
0 votes
0 answers
2
hacker16 asked Dec 17, 2017
276 views
No of states in Min DFA, that accepts (1)* over {0,1} alphabets is1 states2 statesNone of these
1 votes
1 votes
1 answer
3
Prajwal Bhat asked Jan 17, 2017
1,323 views
No. of states in the DFA accepting the following set of strings are:( ( aa* + φ* )* (aa* + φ* ) + bb* + φ* φ + φ* )*Quite confusing to me. Share your approach!