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].

+4 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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,560 answers

146,295 comments

62,306 users