Computation Trees in NFAs
You'll learn how to visualize NFA execution as a branching tree structure where each path represents a different sequence of choices the automaton might take.
The Core Idea
When an NFA reads an input string, it doesn't follow a single deterministic path like a DFA. Instead, it explores multiple possible paths simultaneously. We can visualize this exploration as a computation tree:
- Root: The starting state with the input string
- Branches: Each possible transition choice (including epsilon transitions)
- Nodes: States reached at each step, along with remaining input
- Leaves: Final states after consuming all input
Think of it like exploring a maze where you can clone yourself at every fork. Each clone independently explores one path. If any clone reaches the exit (an accepting state with no input left), you've solved the maze—the NFA accepts the string.
Building the Tree
As the NFA processes input:
- At the root, list all states reachable from the start (including via epsilon transitions)
- For each state, branch on every possible transition for the current input symbol
- Continue branching until all input is consumed
- Mark leaf nodes as accepting (green) or rejecting (red)
Acceptance Rule
The NFA accepts if at least one branch leads to an accepting state after reading the entire input. Even if 99 branches fail, one successful path is enough.
The tree can be infinitely wide (with epsilon loops) or exponentially large, but conceptually it captures all possible computation histories.
Key Takeaway: An NFA's computation tree visualizes all possible execution paths as branches; the string is accepted if any single branch from root to leaf ends in an accepting state.