Nondeterminism

NFAs with choices and ε-moves, the subset construction that turns them into DFAs, and minimisation, which finds the smallest DFA for a language.

About 5 hours of study

Learning objectives

Lessons

  1. 1

    Nondeterministic finite automata (NFA) Intermediate

    An NFA may have several moves, or none, for a symbol, and ε-moves that read nothing. It accepts if any path accepts. Simulate one in Python by tracking the set of states it could be in.

  2. 2

    From NFA to DFA: the subset construction Advanced

    Every NFA can be turned into a DFA whose states are sets of NFA states. Build that DFA in Python, see why it can be exponentially larger, and why NFAs and DFAs recognise the same languages.

  3. 3

    Minimising a DFA Advanced

    Remove unreachable states, then merge states that no input can tell apart, by splitting groups until they are stable. The result is the smallest DFA for the language, and it is unique.

Module practice

Module quiz

1. An NFA may have which of these that a DFA may not?
2. When simulating an NFA, what do you track after each symbol?
3. In the subset construction, what is the DFA's start state?
4. Why does partition refinement start with exactly two groups?
5. Two states move to different groups on the symbol a. What follows?
6. The NFA for 'the 5th symbol from the end is a' has 6 states. How many states does its minimal DFA need?

‹ Strings and finite automataRegular expressions and their limits ›