Q2Theory of Computation
Question
2 marks
What is a Non-deterministic Finite Automata (NFA)?
Answer
NFA allows multiple next states for one input.
A Non-deterministic Finite Automata (NFA) is an FA where for a given state and input symbol, the transition function can point to a set of possible next states (including none or multiple). NFAs are equivalent in power to DFAs.