Finite Automaton

Build DFAs and NFAs — click canvas to add states, draw transitions, test strings

Example:

Test string:

Enter a string and click Run or Step

A deterministic finite automaton (DFA) accepts or rejects strings over an alphabet. The Myhill-Nerode theorem characterizes exactly which languages are regular. NFAs (nondeterministic) accept the same class of languages but can be exponentially more compact.