nondeterministic finite automata
(60 minutes to learn)
Summary
Nondeterministic finite automata are a model of computation that generalizes (deterministic) finite automata. Each state is allowed multiple transitions for a given input character, and the automaton accepts the input if there is any legal sequence of transitions which ends in an accepting state. While NFAs appear more powerful than DFAs, the two are provably equivalent in terms of the languages they can represent.
Context
This concept has the prerequisites:
- finite automata (Nondeterministic finite automata are a generalization of (deterministic) finite automata)
Goals
- Formally define a nondeterministic finite automaton
- Using the subset construction, show that deterministic and nondeterministic finite automata are equivalent
Core resources (read/watch one of the following)
-Free-
→ Coursera: Automata
An introductory course on automata and the theory of computation.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 1.2, "Nondeterminism," pages 47-63
Additional dependencies:
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 2.3, "Nondeterministic finite automata," pages 55-68
See also
-No Additional Notes-