DFA Minimisation Generator
Two states of a finite automaton are equivalent when no string at all leads one to accept and the other to reject — and when that is true, they can be merged without changing the language. This generates a machine, finds those states by refinement, and then does the thing that actually settles it: runs every string up to a given length through both machines and confirms they agree on all of them.
What this generator does
Builds a random automaton over a two-letter alphabet, discards unreachable states, and repeatedly splits the states into groups until no group contains two states that behave differently. Both machines are then run over every short string.
How to use this tool
- Choose how many states the machine should have.
- Generate, and read how many states survived.
- Look at the merged column: those states were indistinguishable.
- Re-run to find machines that were already minimal.
Understanding the controls
- How many states
- Between 2 and 8. Larger machines are likelier to contain states that no string can distinguish, which is when minimisation has something to do.
- Seed
- Reproduces the same machine, which matters when the output is being used as an exercise with a known answer.
Common use cases
- Producing minimisation exercises with a verifiable answer
- Teaching state equivalence as a testable property
- Generating automata for a compilers or theory course
- Checking a minimisation implementation against known output
- Showing that minimisation preserves the language exactly
How this generator works
Start by splitting the states into accepting and non-accepting, since the empty string already tells those apart. Then repeatedly split any group whose members disagree about which group they move to on some symbol. When nothing splits further, each group is a single state of the minimal machine. That construction is standard, and it is not what the tool relies on: before display, every string up to a fixed length is run through both the original and the minimised machine, and they must agree on every one. Every pair of surviving states is also checked to be genuinely distinguishable, which is what minimal means.
Randomness and fairness
Uses your browser's cryptographic random source to build the machine by default. A seed switches to a reproducible sequence, which is deterministic and not cryptographically secure.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- The alphabet is two symbols, which keeps the exhaustive check tractable — a larger alphabet grows the string count exponentially.
- Machines are generated at random, so many turn out already minimal or trivially collapse to one state.
- Only complete deterministic automata are handled: non-deterministic machines need determinising first, which is a separate step.
- The equivalence check runs strings up to a bounded length rather than all strings, which is sound for machines this small.
Privacy and your data
Machines are generated and minimised in your browser and never transmitted, stored or included in analytics.
Related generators
- State Transition Path GeneratorDescribe a state machine and walk random valid paths through it, to find the routes your tests are not covering.
- Regex Pattern Sample GeneratorA common validation regex paired with a real string it matches, for testing or learning pattern syntax.
- Graph Traversal GeneratorThe same graph visited breadth-first and depth-first side by side, with the hop count each node sits at.
- Turing Machine SimulatorA binary increment machine run step by step, with the finished tape checked as a number: the output must be the input plus one.
- Sorting Network GeneratorBuilds a fixed sequence of compare-and-swap steps that sorts any input, verified against every possible sequence of zeroes and ones.