Finite State Machine Designer

Build DFA and NFA diagrams, test strings step by step, and inspect conversion, minimization, and equivalence results.

Results are calculated automatically as you enter data.

Add transition
Transition table
From Symbol To

Drag states and transition markers directly on the canvas.

Start Accept Transition Self-loop

Input is processed as Unicode grapheme symbols.

Simulation Ready to simulate.
Analysis
DFA conversion and minimization
Regular expression and state equivalence

▼ See explanations and tips below ▼

Related Calculators

What Is a Finite State Machine?

A finite state machine is a model that describes a system as a limited set of states connected by labeled transitions. The machine starts in one state, reads an input string symbol by symbol, follows the transition rules, and then accepts or rejects the string depending on where it ends.

In automata theory, this kind of finite state machine is usually called a finite automaton. It is useful because it turns a question about patterns into a precise graph-based model. Instead of saying “this string follows the rule,” you can build states for the important situations, transitions for each input symbol, and accepting states for the situations that count as a match.

For example, a finite automaton can recognize whether a binary string ends in 1, whether a word contains a certain substring, or whether a simple token in a programming language has a valid form. The machine does not remember the whole input. It only remembers its current state, which is why finite automata are powerful for regular patterns but limited for tasks that require unbounded memory.

Why Finite State Machines Matter

Finite state machines are one of the first formal models students meet in theory of computation because they connect diagrams, tables, algorithms, and proofs. A state diagram is visual, but it can also be written as a precise mathematical object. That makes finite automata useful for both learning and implementation.

They appear in practical areas such as lexical analysis, simple protocol design, input validation, user-interface flows, and pattern matching. They are also the foundation for regular languages and regular expressions, which are central ideas in compilers, text processing, and formal language theory.

A finite state machine also helps prevent vague reasoning. When the states, alphabet, start state, accept states, and transitions are explicit, it becomes easier to test examples, find missing transitions, identify unreachable states, and compare two machines that are supposed to recognize the same language.

Key Terms to Know

  • State: A named position or situation in the machine, such as q0 or q1.
  • Alphabet: The set of input symbols the machine is allowed to read, often written as \(\Sigma\).
  • Input string: A finite sequence of symbols from the alphabet, often written as \(w\).
  • Start state: The state where simulation begins, often written as \(q_0\).
  • Accept state: A final state that makes the input accepted if the machine finishes there.
  • Transition: A labeled arrow from one state to another.
  • DFA: A deterministic finite automaton. For each current state and input symbol, there is at most one next state in the transition structure being simulated.
  • NFA: A nondeterministic finite automaton. It may have more than one possible next state for the same state and symbol, and it may use epsilon transitions.
  • Epsilon transition: A transition that consumes no input symbol, usually written as \(\epsilon\) or shown as eps.
  • Epsilon closure: The set of states reachable from a state or state set by taking only epsilon transitions.
  • Reachable state: A state that can be visited from the start state by following transitions.
  • Trap state: A state that loops back to itself for every alphabet symbol, so once the machine enters it, the current transition rules keep it there.
  • Regular language: A set of strings that can be recognized by a finite automaton.
  • Regular expression: A symbolic way to describe a regular language using operations such as union, concatenation, and Kleene star.

How Finite Automata Work

A finite automaton is commonly described as a 5-part object:

$$ M = (Q, \Sigma, \delta, q_0, F) $$

Where:

  • \(Q\) is the finite set of states.
  • \(\Sigma\) is the input alphabet.
  • \(\delta\) is the transition rule.
  • \(q_0\) is the start state.
  • \(F\) is the set of accept states.

For a complete DFA, the transition rule tells the machine exactly which state to move to after reading a symbol from a given state. In a partial diagram, a missing transition means there is no valid next state for that step. If the input string is \(w\), the machine accepts \(w\) when the state reached after reading all of \(w\) is in \(F\).

A compact way to write that idea is:

$$ \hat{\delta}(q_0, w) \in F $$

Here, \(\hat{\delta}\) means the transition rule extended from one symbol to a whole string.

NFAs work differently. Instead of tracking one current state, an NFA simulation tracks a set of possible current states. If epsilon transitions are allowed, the simulation begins with the epsilon closure of the start state:

$$ S_0 = \epsilon\text{-closure}(\{q_0\}) $$

After reading the next input symbol \(c\), the new set of possible states is:

$$ S_{i+1} = \epsilon\text{-closure}(\operatorname{move}(S_i, c)) $$

The input is accepted if at least one possible current state is accepting after all symbols have been processed:

$$ S_n \cap F \ne \varnothing $$

This is the key idea behind NFA simulation: the input does not need every possible path to succeed. It is accepted if at least one valid path reaches an accept state at the end.

DFA and NFA Conversion

Every NFA has an equivalent DFA that recognizes the same language. The standard conversion is called subset construction. Each state in the new DFA represents a set of states from the original NFA.

If the NFA has \(n\) states, the converted DFA can theoretically have as many as:

$$ 2^n $$

states, because there are \(2^n\) possible subsets of an \(n\)-state set. In many examples, only a small number of those subsets are reachable. In large or highly nondeterministic machines, however, the number can grow quickly.

DFA Minimization

DFA minimization reduces a deterministic automaton to an equivalent DFA with fewer states when some states behave the same for all possible continuations of the input. A common approach starts by separating accepting states from rejecting states, then repeatedly refines those groups according to where transitions go.

The basic idea is:

  1. Put accepting and non-accepting states into separate groups.
  2. Compare how states in the same group behave on each alphabet symbol.
  3. Split a group when its states transition into different groups.
  4. Repeat until no more useful splits are found.
  5. Treat each remaining group as one state in the minimized DFA.

A minimized DFA is easier to inspect because equivalent behavior has been merged.

Regular Expressions from Automata

Finite automata and regular expressions describe the same class of languages: regular languages. One way to convert an automaton to a regular expression is state elimination. The method rewrites paths through the machine while removing intermediate states, leaving a regular expression that describes the same accepted strings.

State elimination is mechanical, but the resulting expression can become long. Different elimination orders can also produce different-looking expressions for the same language. For that reason, regular-expression generation is most practical for small machines.

Examples of Finite State Machines in Practice

Example 1: A DFA That Accepts Binary Strings Ending in 1

Suppose the alphabet is:

$$ \Sigma = \{0, 1\} $$

Use two states:

  • q0: the string seen so far is empty or ends in 0.
  • q1: the string seen so far ends in 1.

Let q0 be the start state and q1 be the only accept state.

The transition table is:

Current state Input 0 Input 1
q0 q0 q1
q1 q0 q1

For the input 101, the path is:

$$ q0 \xrightarrow{1} q1 \xrightarrow{0} q0 \xrightarrow{1} q1 $$

The machine ends in q1, which is accepting, so 101 is accepted.

For the input 100, the path is:

$$ q0 \xrightarrow{1} q1 \xrightarrow{0} q0 \xrightarrow{0} q0 $$

The machine ends in q0, which is not accepting, so 100 is rejected.

Example 2: An NFA with an Epsilon Transition

Consider a machine with start state q0 and accept state q1. If there is an epsilon transition from q0 to q1, then the epsilon closure of the start state is:

$$ \epsilon\text{-closure}(\{q0\}) = \{q0, q1\} $$

Because the current state set already contains the accept state q1, the empty input string is accepted.

This is different from reading an actual symbol. An epsilon transition changes the possible state set without consuming a character from the input.

Example 3: When No Valid Path Remains

Suppose the alphabet is:

$$ \Sigma = \{0, 1\} $$

If the input is 102, the symbol 2 is outside the alphabet. The simulation should reject the input because there is no valid transition rule for a symbol the machine does not recognize.

In an NFA trace, another common edge case is the empty current set:

$$ S_i = \{\} $$

That means no possible path remains after the input prefix processed so far. Once the current set is empty, the machine cannot later recover unless the simulation model explicitly provides a path, which a standard finite automaton transition step does not do from no states.

How to Interpret the Result

An Accepted result means the machine finished processing the whole input with at least one accepting possibility. For a DFA, that means the single final state is an accept state. For an NFA, it means the final set of possible states contains at least one accept state.

A Rejected result means the input did not end in an accepting state or state set. It may also mean the input contained a symbol outside the alphabet.

A trace shows how the current state or state set changes as the input is processed. State sets are displayed in braces, such as {q0, q2} or {}. For an NFA, a trace entry such as {q0, q2} means both q0 and q2 are possible after the listed input step. An entry of {} means no valid path remains for that processed prefix.

The displayed determinism analysis is about the actual transition structure. A machine is nondeterministic if it has an epsilon transition or more than one transition with the same from-state and symbol. This can differ from the selected editing mode if the transition structure itself contains nondeterministic features.

Reachable states are states that can be visited from the start state. Unreachable states may still appear in a diagram, but they do not affect which input strings are accepted unless the start state or transitions change.

DFA states created by subset construction represent sets of original NFA states. A converted DFA state named with multiple original states should be read as “the NFA could be in any of these states at this point.”

Minimized state groups show states that the minimization process treats as equivalent. If two states end up in the same group, the minimized DFA can merge them without changing the accepted language.

A generated regular expression describes the same accepted language only when the conversion is available for the current machine size and structure.

Common Mistakes and Misconceptions

One common mistake is putting eps, epsilon, ε, or a blank entry in the alphabet. Those labels are reserved for epsilon transitions. The ordinary letters e and E remain available as input symbols.

Another mistake is assuming that an NFA accepts only when all paths accept. An NFA accepts when at least one possible path reaches an accept state after the entire input is consumed.

It is also easy to confuse the selected DFA or NFA mode with the actual transition structure. A diagram with duplicate transitions for the same state and symbol is nondeterministic, even if someone intended to build a DFA. A diagram with epsilon transitions is also nondeterministic.

When every alphabet symbol is one Unicode grapheme, the simulator reads an ordinary string one grapheme at a time, so an emoji or composed character counts as one symbol. If any alphabet symbol contains multiple graphemes, enter the test input as whitespace-separated tokens.

Another frequent issue is forgetting to mark an accept state. A machine with no accept states cannot accept any input string, even if the transitions look reasonable.

For imported transitions, the referenced states must already exist. Importing transition rows is not the same as importing a complete machine definition with new states.

When to Use Finite State Machines

Use finite state machines when a problem can be described by a finite number of situations and symbol-by-symbol transitions.

Common uses include:

  • Testing whether strings match a regular pattern.
  • Learning DFA and NFA behavior in theory of computation.
  • Comparing a state diagram with its transition table.
  • Checking reachability, trap states, and accepting states.
  • Demonstrating how nondeterminism and epsilon transitions work.
  • Converting an NFA to a DFA to understand subset construction.
  • Minimizing a DFA to simplify equivalent behavior.
  • Exploring the relationship between finite automata and regular expressions.

Finite state machines are especially helpful when the important memory of the system can be summarized by the current state. They are not the right model when the task requires an unbounded stack, arbitrary counting, or memory of an unlimited amount of previous input.

Limitations and Things to Keep in Mind

Finite automata recognize regular languages. They cannot model every possible pattern. For example, languages that require matching an arbitrary number of nested or paired structures generally need a stronger model than a finite automaton.

This calculator supports two explicit input modes. Single-grapheme alphabets use ordinary strings; alphabets containing a multi-character symbol use whitespace-separated input tokens. Longest-match guessing is never used.

Whitespace and commas cannot be alphabet symbols because they delimit alphabet entries and multi-character input tokens. Alphabet symbols and input are normalized to Unicode NFC before matching.

In DFA mode, epsilon transitions and conflicting targets for the same state and symbol are validation errors. Identical duplicate edges are safely deduplicated, but conflicting data is never silently deleted.

Subset construction can grow quickly. This calculator caps NFA-to-DFA conversion at 32 DFA states. If the cap is reached, conversion is labeled truncated and minimization and equivalence claims are withheld.

Regular-expression generation is limited to small machines. This calculator attempts state elimination only for machines with 7 or fewer states. If a regular expression is not generated for a larger machine, that is a practical size limit rather than proof that no equivalent regular expression exists.

In generated regular expressions, safe single-character symbols use ordinary notation. Multi-character or punctuation symbols appear as delimited atoms such as ⟨token⟩, meaning one alphabet symbol rather than a sequence of characters.

Deleting the only remaining state is blocked so the machine always has at least one state. Imported transitions must refer to existing states, and invalid transition rows are ignored.

Graph export and clipboard actions can depend on browser permissions and browser support. If those actions fail, the automaton itself may still be valid.

How to Use This Calculator

  1. Choose DFA or NFA mode.
  2. Enter the alphabet as comma-separated or whitespace-separated symbols. The calculator will indicate whether input uses graphemes or whitespace-delimited tokens.
  3. Build the state diagram by adding states, selecting the start state, and marking accept states.
  4. Add transitions by choosing a from-state, transition symbol, and to-state, or edit/import transition rows in from, symbol, to format.
  5. Enter the input string to test.
  6. Run the simulation all at once or step through it one symbol at a time.
  7. Review the result, trace, determinism analysis, reachable states, trap states, DFA conversion, minimized groups, and regular-expression output when available.
  8. Copy the machine summary or download the graph image if your browser supports those actions.

Frequently Asked Questions

What is the difference between a DFA and an NFA?

A DFA has no epsilon transitions and does not branch into multiple next states for the same state and input symbol. An NFA can have multiple possible next states and may include epsilon transitions. Both models recognize exactly the regular languages, but NFAs can be more compact and easier to design.

Does an NFA accept only if every path reaches an accept state?

No. An NFA accepts an input when at least one possible path reaches an accept state after the entire input is processed. Paths that fail do not matter if another valid path succeeds.

What does epsilon closure mean?

The epsilon closure of a state or set of states is the set of states reachable by taking only epsilon transitions, including the original state or states. It matters because epsilon transitions do not consume input, so they must be considered before reading a symbol and after each symbol is processed.

Why can converting an NFA to a DFA create many states?

Subset construction represents each DFA state as a set of NFA states. An NFA with \(n\) states has up to \(2^n\) possible subsets, although not all of them are always reachable. This is why conversion can be simple for small examples but large for some machines.

Why did the regular expression not appear?

Regular-expression generation can become large and hard to read. This calculator only attempts state elimination for machines with 7 or fewer states. A missing expression for a larger machine usually means the size cap was reached, not that the language has no regular expression.

What does a trap state mean?

A trap state is a state that loops to itself on every alphabet symbol under the current transition rules. Once the machine enters that state, every remaining input symbol keeps it there. Trap states are often used to represent “already failed” situations in a complete DFA.

Sources and References

Books

  1. Michael Sipser. Introduction to the Theory of Computation. 3rd ed., Course Technology/Cengage Learning, 2012. Chapter 1, “Regular Languages,” especially finite automata, nondeterminism, regular expressions, and regular-language equivalences. ISBN 978-1133187790. Author's book page.
  2. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 2nd ed., Addison-Wesley, 2001. Chapters 2–3, “Finite Automata” and “Regular Expressions and Languages.” ISBN 978-0201441246. Google Books record.

Online and Official Sources

  1. JFLAP. “Building Your First Finite Automaton.” Accessed June 28, 2026.
  2. JFLAP. “Converting a NFA to a DFA.” Accessed June 28, 2026.
  3. JFLAP. “Converting a DFA to a Minimal State DFA.” Accessed June 28, 2026.
  4. JFLAP. “Converting a FA to a Regular Expression.” Accessed June 28, 2026.
  5. Jae-Hee Ahn and Yo-Sub Han. “Implementation of State Elimination Using Heuristics.” Implementation and Application of Automata, Lecture Notes in Computer Science, vol. 5642, Springer, 2009, pp. 178–187. Springer Link.