Skills101
← All practice quizzes

Quiz: NFA and Subset Construction

5 questionsNo time limitPass: 60%+10 XP on first pass

What nondeterminism means, NFAs and ε-NFAs, why they're easier to design, how to simulate them by tracking sets of states, and the subset construction that converts any NFA into an equivalent DFA — implemented step by step in Python with a worked exam example.

Log in to take the quiz

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

  1. Question 1

    When does an NFA accept a string?

  2. Question 2

    What is ε-closure(A) in the demo?

  3. Question 3

    An NFA has n states. At most how many states can the DFA from subset construction have?

  4. Question 4

    In the "ending in ab" conversion, which DFA states are accepting?

  5. Question 5

    Compared with DFAs, NFAs recognise: