DFA simulator: build a finite automaton and test strings

Build a deterministic finite automaton (DFA) and run strings through it. Edit the transition table, drag the states to tidy the diagram, step through a run one symbol at a time, and test a whole list of strings at once. When the machine is right, copy a link that opens it exactly as it is.

Interactive: DFA editor, step-by-step simulator and batch testerUpdated 5 November 2026

DFA simulatorEdit the transition table, drag states to tidy the diagram, then run a string through it.

Pseudocode

q ← start state
for each symbol c of the input, left to right:
if δ(q, c) is undefined: reject (fall into the dead state)
q ← δ(q, c)
accept if q is an accepting state, otherwise reject

Result

Run a string to see the verdict.

Checks

Shortest accepted strings

Test many strings

1 / 1

How to use the simulator

Start from a preset or from the default machine. The presets cover parity, divisibility, suffixes, substrings and a partial DFA.
Set the alphabet: one to four single characters, separated by commas.
Edit the table. Each row is a state. Pick the start state with the radio button, tick accepting states, rename states, and choose where each symbol leads. Leave a cell as “— (dead)” to send that move to an implicit dead state.
Run a string. Type it and press Run, then use the controls (or the arrow keys and Space) to step forwards and backwards. The tape shows the symbol being read and the diagram highlights the transition taken.
Batch-test by typing strings into the “Test many strings” box, one per line. An empty line tests the empty string ε.
Share with “Copy share link”. The link holds the whole machine, including state positions, so nothing is stored on a server.

What the checks tell you

As you edit, the simulator checks the machine and lists:

Missing transitions. A DFA is strictly a total function $\delta : Q \times \Sigma \to Q$ . Many textbooks allow a partial table and treat each missing move as going to a dead state, and so does the simulator. Fill in every cell if your course requires a complete DFA.
Unreachable states, which no input can reach from the start. They never affect the language and can be deleted.
Whether the DFA is minimal. The simulator runs Moore’s partition refinement in the background and tells you how many states an equivalent minimal DFA needs. If yours has more, two of its states are indistinguishable.
The shortest accepted strings, in length-then-alphabetical order. This is the quickest sanity check of a design: if ε appears and shouldn’t, the start state should not be accepting.

Worked example: binary multiples of 3

Choose the “Binary multiple of 3” preset. Each state stores the value read so far modulo 3, and reading bit $b$ in state $r$ moves to $(2r + b) \bmod 3$ . On input 1001 (nine) the run visits r0 → r1 → r2 → r1 → r0 and ends in r0, so it accepts. The shortest accepted strings are ε, 0, 00, 11, 000, 011: every one is a multiple of 3 in binary (with leading zeros allowed), and ε counts as zero because the start state is accepting.

Designing a DFA that passes the tests

The key question is what does the machine need to remember? Each state should stand for one answer to that question. For “ends in ab” the answers are “nothing useful”, “just read a” and “just read ab”, so three states. A good habit is to write the meaning of each state as its name, as the presets do, and then check every transition against that meaning: “if I have just read a and now read b, I have just read ab”.

Then test systematically. Include the empty string, the shortest strings that should be accepted, strings that are almost right (one symbol off), and a long string. The batch tester shows a tick or a cross for each, so a list of a dozen test strings catches most mistakes in seconds.

DFA or NFA? This simulator is for deterministic machines: one next state per state and symbol. If your design needs several possible next states or ε-moves, it is an NFA. Build it in the NFA to DFA converter, which turns it into a DFA you can open here with one click. To start from a regular expression instead, use the regex to NFA converter.

Formal definition

A DFA is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$ : a finite set of states, an alphabet, a transition function, a start state and a set of accepting states. It accepts a string $w = w_1 w_2 \cdots w_n$ when the run $q_0, \delta(q_0, w_1), \delta(\delta(q_0, w_1), w_2), \dots$ ends in $F$ . The finite-state machines explainer covers this in detail, along with regular languages and what DFAs cannot do.

References

M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2012. Section 1.1.
J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006. Chapter 2.