Nondeterministic finite state machine
A state machine where input may cause transitions to multiple states or enable epsilon transitions. NFAs are more expressive in notation than DFAs but recognize identical languages. NFAs can be converted to DFAs.
Real World
Google's search engine internally converts the regex you type into an NFA (with epsilon transitions), then converts it to a DFA for fast matching across billions of web pages.
Exam Focus
When tracing an NFA, show all possible paths — it accepts if at least one path reaches an accepting state.
How well did you know this?