# 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-