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:

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.
Author: Jeffrey D. Ullman

-Paid-

See also

-No Additional Notes-