Theory of Computation (Automata)
Non-deterministic finite automaton (NFA) is best defined as which of the following?
- A. A sequence of characters that defines a search pattern, corresponding to regular languages.
- B. A formal grammar in which every production rule has a single non-terminal on its left-hand side.
- C. A finite automaton that may have multiple possible transitions for a given state and input symbol. ✓
- D. The undecidable problem of determining whether a given program will finish running or continue forever.
Correct answer
C. A finite automaton that may have multiple possible transitions for a given state and input symbol.
Explanation
Non-deterministic finite automaton (NFA) refers to a finite automaton that may have multiple possible transitions for a given state and input symbol.