Deterministic and nondeterministic finite automata

Last update: 2011-02-04

This page is not intended to explain the entire theory; it provides a state machine for testing automata. You can start learning about finite-state machines here, then read more here, here, and here.

This topic is essential for anyone interested in programming digital circuits or formal languages. Automata are also fundamental to regular-expression recognizers, even if you have never studied them directly.

Enter the parameters below to test whether a word is recognized. The page also includes a nondeterministic-to-deterministic automaton converter. Both machines are prefilled with an example—feel free to try them.

Deterministic finite-state machine

Deterministic finite automaton DFA = (Σ, S, s₀, δ, F)
={}
(automaton states separated by commas)
={}
(alphabet separated by commas)
={}
(initial state)
={}
(final states separated by commas)
(transition functions, one per line in the format: current state > consumed character > next state)
=""
(word to test)

Nondeterministic finite automaton converter

NFA to DFA
={}
(automaton states separated by commas)
={}
(alphabet separated by commas)
={}
(initial state)
={}
(final states separated by commas)
(transition functions, one per line in the format: current state > consumed character > next state)
Log
When you test a word, the recognition steps will appear here