NFA Definition and Components
What you'll learn: You'll discover what nondeterministic finite automata are, their formal structure, and how they differ from the deterministic automata you've already studied.
What is an NFA?
A Nondeterministic Finite Automaton (NFA) is a computational model similar to a DFA, but with a crucial superpower: it can have multiple possible next states for a given input symbol, or even transition without consuming any input at all.
Think of it like choosing your path in a maze. A DFA is like following strict signs—each sign gives you exactly one direction. An NFA is like having a magic ability to explore multiple paths simultaneously or teleport ahead without following the path.
The Five-Tuple Notation
Like DFAs, NFAs are formally defined as a five-tuple:
NFA = (Q, Σ, δ, q₀, F)
- Q: Finite set of states
- Σ: Input alphabet
- δ: Transition function (this is where NFAs differ!)
- q₀: Start state (in Q)
- F: Set of accepting states (subset of Q)
The Key Difference: Transition Functions
Here's what makes NFAs nondeterministic:
DFA transition function: δ: Q × Σ → Q
Maps a state and symbol to exactly one next state.
NFA transition function: δ: Q × (Σ ∪ {ε}) → P(Q)
Maps a state and symbol (or ε, the empty string) to a set of possible states (the power set of Q).
This means an NFA can:
- Have zero, one, or many transitions for the same state-symbol pair
- Make ε-transitions (move without reading input)
- "Guess" which path to take
Key Takeaway: NFAs extend DFAs by allowing nondeterministic transitions—multiple next states or empty-string transitions—making them more flexible for expressing patterns, though ultimately equivalent in computational power.