The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

Ques:- Let ∑= {0, 1} What will be the number of states in minimal DFA, if the Binary number string is congruent to (mod 8)?

*[ Can anybody explain this as I am getting 8 states for this since remainders will be 8 (0,1,2,3,4,5,6,7). But the answer is 4].

*[ Can anybody explain this as I am getting 8 states for this since remainders will be 8 (0,1,2,3,4,5,6,7). But the answer is 4].

+3 votes

0 votes

MDFA, for binary strings congruent to (mod 8) for input $\sum$(0,1) as follow:

transcation table:

states | 0 | 1 |

Q_{0} |
Q_{0} |
Q_{1} |

Q_{1} |
Q_{2} |
Q_{3} |

Q_{2} |
Q_{4} |
Q_{5} |

Q_{3} |
Q_{6} |
Q_{7} |

Q_{4} |
Q_{0} |
Q_{1} |

Q_{5} |
Q_{2} |
Q_{3} |

Q_{6} |
Q_{4} |
Q_{5} |

Q_{7} |
Q_{6} |
Q_{7} |

In here, binary string r(mod n),number of states is depends on remainder & final state is Q_{r.}

from table 4 equal states such as Q_{0} =Q_{4} ,Q_{1} =Q_{5} ,Q_{2} =Q_{6},Q_{3} =Q_{7.}

So MDFA contain 4 states.

0

Hi Thanks for the answer but recently I had discovered a flaw in your answer.

If you use 'Minimization of DFA' technique where we make 0equivalence,1equivalence states. You will not get q0 = q4, q1=q5,... as you have mentioned.

Your answer is correct but not the method.

The minimized DFA states after 'Minimization of DFA' are [q0],[q4],[q1,q3,q5,q7],[q2,q6].

where q0 is initial and final state and according to these minimized states we can say that "q0 and q4 are independent" and "q1,q3,q5,q7 are equal" and also "q2 and q6 are equal".

Please correct me if I am wrong.

Thanks

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 448
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,964 questions

45,466 answers

131,328 comments

48,379 users