Grape

Home

❯

10 Zettels

❯

Theorem All DFAs have an equivalent NFA

Theorem - All DFAs have an equivalent NFA

Sep 23, 20251 min read

  • zettel

Theorem - All DFAs have an equivalent NFA

Statement

Every Deterministic Finite Automaton has an equivalent Nondeterministic Finite Automaton.

Proof

The proof is that, by definition: every DFA is also an NFA. It just so happens that DFAs do not make use of the extra “power” or flexibility of NFAs


Graph View

  • Theorem - All DFAs have an equivalent NFA
  • Statement
  • Proof

Backlinks

  • Week 3

Created with Quartz v4.5.2 © 2025

  • GitHub
  • LinkedIn