The subset construction starts from the ε-closure of the NFA's start state. For every new DFA state T and every symbol a, it computes ε-closure(move(T, a)). Each new subset becomes a new DFA state. Step through it and watch both diagrams.
Keyboard: ← → to step, Space to play or pause. Expand a diagram to present it full screen.
DFA transition table δD
→ marks the start state, * marks accepting states. A DFA state accepts when its subset contains at least one NFA final state.
Moore's partition refinement. Start with two groups, accepting and non-accepting states (Π₀). In each round, split a group when two of its states move to different groups on some symbol. When a round splits nothing, each group becomes one state of the minimal DFA.