Nondeterministic Finite Automata (NFA)
An NFA is like a DFA, but with superpowers. For any state and input symbol, an NFA can have zero, one, or multiple transitions. It can also have epsilon (ฮต) transitions that allow it to move between states without consuming any input. Think of it as a machine that can "clone" itself and explore all possible paths simultaneously.
An NFA accepts a string if there exists at least one path from the start state to an accept state. Even if some paths lead to rejection, one successful path is enough.
Formal Definition
An NFA is a 5-tuple (Q, ฮฃ, ฮด, q0, F) where ฮด: Q ร (ฮฃ โช {ฮต}) โ P(Q). The transition function returns a set of states (the power set of Q), meaning from any state-symbol pair, you can transition to zero, one, or multiple states.
NFA for strings ending in "01" or "10":
q0 --0--> {q0, q1}
q0 --1--> {q0, q2}
q0 --ฮต--> {}
q1 --1--> {q3} (for "01" pattern)
q2 --0--> {q3} (for "10" pattern)
q3 --0--> {}
q3 --1--> {}
Start: q0
Accept: {q3}
Trace "01":
q0 โ(0) {q0, q1}
From q0: โ(1) {q0, q2}
From q1: โ(1) {q3} โ accept!
Trace "10":
q0 โ(1) {q0, q2}
From q0: โ(0) {q0, q1}
From q2: โ(0) {q3} โ accept!DFA vs NFA
Every DFA is technically an NFA โ one that happens to have at most one transition per symbol. But NFAs are much more flexible. Consider the language of strings containing "01" or "10". An NFA can split into two parallel paths from the start state and check both patterns simultaneously. A DFA would need more states to track which pattern it's currently matching.
Despite this flexibility, NFAs and DFAs recognize exactly the same class of languages: the regular languages. The trade-off is that NFAs are easier to design but harder to simulate (you must track all possible states), while DFAs are harder to design but simpler to simulate (just follow the single transition).
NFA Acceptance
An NFA accepts a string w if and only if there exists at least one computation path that starts at the start state, consumes all of w, and ends in an accept state. If no such path exists, the string is rejected.
This is why NFAs are called "nondeterministic" โ the machine doesn't "choose" which transition to follow. Mathematically, we say a string is accepted if the set of reachable states after consuming the entire string contains at least one accept state.