Minimal FA

Question

What is the number of states in a minimal FA which accepts all strings over (0,1)* where every string starts with 100 and the length of the string is congruent to 1(mod4)

I am getting 11 states. Ans given is 8. While doing the cross product , is it ensured that , I will get the minimal DFA ? or do I have to minimise after the cross product ?

Comments

i have got 7 states

Answer 1

there are 8 states inclusive of dead state , sorry for the small size but I tried resizing it but it is not getting uploaded then ,But I hope its clear , u can open the image in new link tab.

And after cross-product you might need to minimize. 

Comments

Hi as you answred the question ,, then your diagram also going to accept 10000 ,which equal 16 i.e, 0mod4

But in the question the string with 1mod4 will be accepted.

for 10001=17  i.e, 1mod4 is right

but for 10000 your digram is accepting how it is possible

Answer 2

answer is 7

i dunt know why yur answer is having two trap states!! plz tell

Answer 3

8 is the right answer
(start with q0)
starting with 100 which implies we cannot make q1 as the final state hence we have to make q4 the 5th state as final state.

beacuse 5mod4=1 so q5 =6mod4 q6=7mod4 and q7=8mod4 at 8th state i.e q7 make trasition to q5th because 9=1mod4...

Answer 4

Caption

Comments

But your DFA will not except 10000.

which should be accepted as its length is 5 and 5 mod 4 = 1.