Skills101
← All practice quizzes

Quiz: DFA Minimisation (Table Filling)

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

The table-filling (Myhill–Nerode) method for minimising a DFA, done the way exams expect — round by round on a classic 8-state machine — then simulated in Python, with the shortest string that tells two states apart and a program that checks whether two DFAs accept the same language.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    In the table-filling method, which pairs are marked in round 0?

  2. Question 2

    Why is state D removed before filling the table in the example?

  3. Question 3

    An unmarked pair (p, q) goes on symbol 1 to the pair (C, F), which is marked. What do you do?

  4. Question 4

    How many states does the minimal DFA for the 8-state example have?

  5. Question 5

    A pair is first marked in round 2. What is the length of its shortest distinguishing string?

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →