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
- Simulate NFAs with sets of states and ε-closures
- Convert an NFA into an equivalent DFA
- Remove unreachable states and merge equivalent ones
Lessons
- 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
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
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
- Theory: Does the NFA accept?Easy
- Theory: The NFA's set of statesMedium
- Theory: An NFA with ε-movesHard
- Theory: How many DFA states?Easy
- Theory: The subset construction tableMedium
- Theory: Subset construction with ε-movesHard
- Theory: Unreachable statesEasy
- Theory: The size of the minimal DFAMedium
- Theory: Minimise a DFAHard
Module quiz
‹ Strings and finite automataRegular expressions and their limits ›