🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← All topics

Quiz: DFA Minimisation (Table Filling): questions with answers

10 questions, each with the answer and a short explanation.

Take the timed quiz + get a certificate →
  1. Q1. In the table-filling method, which pairs are marked in round 0?
  2. Q2. Why is state D removed before filling the table in the example?
  3. Q3. An unmarked pair (p, q) goes on symbol 1 to the pair (C, F), which is marked. What do you do?
  4. Q4. How many states does the minimal DFA for the 8-state example have?
  5. Q5. A pair is first marked in round 2. What is the length of its shortest distinguishing string?
  6. Q6. What does this print? (code)
  7. Q7. For n reachable states, how many cells does the triangular table have?
  8. Q8. The equivalence checker returns (False, "01") for two DFAs. What does that mean?
  9. Q9. Which statement about the minimal DFA of a regular language is true?
  10. Q10. What is the main mistake in this reasoning: "δ(p, 0) = B and δ(q, 0) = H are different states, so mark (p, q)"?