Log in
MODULE 19

DFA & NFA Simulator: Finite Automata Calculator

Transitions: state,symbol->target, separated by ;. For NFA, use eps as the symbol for an epsilon transition, and multiple comma-separated targets for non-determinism.

Example above: accepts binary strings ending in "01".

What is DFA / NFA?

Automata theory studies abstract machines and the languages they recognize. A finite automaton (DFA/NFA) is the simplest such machine, sitting underneath every regular expression engine and lexical analyzer.

How Does This Calculator Work?

Choose DFA or NFA mode, enter your states, alphabet, start state, accepting states, and transitions, then enter a test string. The simulator shows every state transition as the string is processed, and whether it's ultimately accepted.

Common Formulas & Rules

  • Finite Automaton (FA): a machine with a finite set of states, a start state, accepting states, and transitions.
  • Deterministic FA (DFA): exactly one transition per state per input symbol.
  • Nondeterministic FA (NFA): a state can have multiple (or zero) transitions for the same symbol; every NFA has an equivalent DFA.
  • Regular language: any language recognizable by a finite automaton, equivalently by a regular expression.
  • Acceptance: a string is accepted if, starting from the start state and following its symbols, the machine ends in an accepting state.

Worked Example

A DFA that accepts binary strings ending in "1" needs just two states: state A (start, also reached on any 0) and state B (reached on 1, accepting). Reading "101": start at A, read 1 → B, read 0 → A, read 1 → B (accepting) — correctly accepted since the string ends in 1.

Study guide: Automata

Written for students learning this topic for the first time. Last updated October 2026.

Overview

Finite automata are the simplest model of computation: a machine with finitely many states that reads a string one symbol at a time and finally accepts or rejects. The languages they recognise are the regular languages, the same ones described by regular expressions.

Key ideas explained

Deterministic finite automata

A DFA is a 5-tuple (Q, Σ, δ, q₀, F): states, alphabet, transition function, start state and accepting states. From every state there is exactly one transition for every symbol, and the machine accepts if it ends in a state of F. Missing transitions are usually sent to a dead state.

Nondeterministic automata

An NFA may have several, zero or ε-transitions from a state, and accepts if some path leads to an accepting state. Every NFA can be converted to a DFA by the subset construction (possibly with up to 2ⁿ states), so NFAs are not more powerful, only sometimes more compact.

What regular languages can and cannot do

Regular languages are closed under union, concatenation, star, complement and intersection. The pumping lemma shows that {aⁿbⁿ} is not regular: a machine with finite memory cannot count without bound. That is why regular expressions cannot match balanced parentheses.

Designing a DFA

Decide what the machine must remember. Parity of 1s needs 2 states. “Ends with 01” needs 3, tracking how much of 01 has just been seen. “Divisible by k” needs k states, one for each remainder.

Worked examples

Even number of 1s

Problem. Design a DFA over {0, 1} accepting strings with an even number of 1s, and run 1011 and 1001.

  1. States E (start, accepting) and O. A 0 keeps the state; a 1 switches it.
  2. 1011: E → O → O → E → O, which ends in O (three 1s) and is rejected.
  3. 1001: E → O → O → O → E, which ends in E (two 1s) and is accepted.

Answer. 1011 is rejected and 1001 is accepted.

Strings ending in 01

Problem. Design a DFA for binary strings ending in 01.

  1. q0: no progress; q1: last symbol was 0; q2 (accepting): last two symbols were 01.
  2. Transitions: q0 –0→ q1, q0 –1→ q0; q1 –0→ q1, q1 –1→ q2; q2 –0→ q1, q2 –1→ q0.
  3. Input 1101 ends in q2 (accepted); input 0100 ends in q1 (rejected).

Answer. The three-state DFA above accepts exactly the strings that end in 01.

Enter these same values in the calculator above and compare each step with the working shown here.

Common mistakes to avoid

  • Leaving out a transition for some symbol in a DFA.
  • Marking the wrong states as accepting. If the start state is accepting, the empty string is accepted.
  • Believing NFAs recognise more languages than DFAs.
  • Forgetting to consider the empty string.
  • Expecting a finite automaton to recognise balanced parentheses or aⁿbⁿ.

Where this shows up in computer science

  • Lexical analysis in compilers and regular-expression engines are based on finite automata.
  • Protocols and user interfaces are specified as state machines, for example TCP connection states.
  • Hardware sequence detectors and control units are finite-state machines.

Test yourself

Try each question before opening the answer.

What language does a one-state automaton that is both start and accepting, with self-loops on every symbol, accept?

All strings over the alphabet (Σ*).

How many states does a DFA for “contains the substring 11” need?

Three: no progress, seen one 1, and seen 11 (accepting, with loops on both symbols).

What is the fewest states of a DFA over {a} accepting strings whose length is divisible by 3?

Three.

Frequently asked questions

What's the difference between a DFA and an NFA?

A DFA (Deterministic Finite Automaton) has exactly one transition per state per input symbol. An NFA (Nondeterministic) can have multiple, or zero, transitions for the same symbol. Every NFA has an equivalent DFA, just potentially with more states.

What is a regular language?

A regular language is any language (set of strings) that a finite automaton can recognize — equivalently, any language describable by a regular expression.

Why can't a finite automaton count arbitrarily high?

A finite automaton has a fixed, finite number of states, so it can't remember an unbounded count. Languages requiring unlimited counting (like "equal numbers of a's and b's") need a more powerful model, like a pushdown automaton.