Nondeterminism: Multiple Transitions and Choices
You'll learn: How NFAs allow multiple transitions from the same state on the same input symbol, enabling computational branching.
The Core Difference from DFAs
In a DFA (Deterministic Finite Automaton), computation follows one clear path: for each state and input symbol, there's exactly one next state. NFAs (Nondeterministic Finite Automata) break this rule — from a given state, reading the same input symbol can lead to multiple possible next states.
What Multiple Transitions Mean
Imagine standing at a fork in a road where both paths are labeled "a". In a DFA, you'd be stuck — ambiguity isn't allowed. In an NFA, you can explore both paths simultaneously. The computation "branches" into multiple parallel possibilities.
For example, an NFA might have:
- State q₁ reading symbol
a→ transitions to q₂ - State q₁ reading symbol
a→ also transitions to q₃
Both transitions exist at the same time. The machine doesn't "choose" one — it conceptually explores all possibilities.
Acceptance Through Any Path
An NFA accepts a string if at least one computational path leads to an accept state. Think of it like solving a maze with the power to clone yourself: if any clone reaches the exit, you win. It doesn't matter if other paths fail.
This nondeterministic choice doesn't make NFAs physically "magic" — it's a mathematical abstraction that simplifies designing automata for complex patterns. Later, you can always convert an NFA to an equivalent DFA that produces the same language.
Key Takeaway: NFAs allow multiple transitions for the same input symbol, creating branching computation where acceptance requires only one successful path among many possibilities.