parallel exploration of paths

Another vivid way to see an NFA is as a machine that, whenever it faces several allowed moves, CLONES itself — one clone per choice — and lets all the clones read the rest of the input in parallel. Each clone follows its own path; clones that get stuck quietly vanish. At the end, if ANY clone is sitting on an accept state, the whole machine accepts. It is like sending an army of explorers down every branch of the maze at once and declaring victory if even one finds the exit.

This cloning picture is mathematically identical to the guess-and-verify picture and to tracking the set of possible states — they are three views of the same thing. The cloning view is the one that explains, very directly, why the subset construction works: at any moment the only thing that matters is the SET of states some clone currently occupies, not how many clones there are or how they got there. That set is finite (it is a subset of Q), which is why a deterministic machine can track it.

It is crucial to be honest about what "parallel" means here. This is parallelism in the mathematical definition, not in real hardware. A physical computer simulating an NFA does the cloning by bookkeeping — keeping a list of active states — and pays for it in time or memory; it does not get a free army of processors. The parallel picture is a thinking aid for understanding acceptance, not a promise of free speed.