Regex state machine visualizer
Type a pattern, see the machine it compiles to, and step a test string through it one character at a time.
- hex colouralternation between two counted repeats
- ISO datecounted repeats and escapes
- email-ishcharacter classes and an open-ended repeat
- greedy trapwhere this machine and your language disagree
- loopsa group under a star, drawn as a cycle
Circles are states. Solid arrows consume one character and are labelled with the slice of the pattern that produced them. Dashed arrows are empty moves, the machine changing state without reading anything. Dotted arrows are anchors: they consume nothing but only pass at the start or end of the input. A double circle accepts.
Colour repeats what the shapes and the step readout already say. Bright green is the path that matched, amber is where the machine stands at this step, red is where it ran out of transitions, and dim green is a state this run never reached.
Transition table
What the parser accepts
This is the whole grammar. Anything not on this list is either treated as a literal character or refused with a reason, and nothing is silently ignored except laziness.
| Syntax | What it means here | Example |
|---|---|---|
a | A literal character. Anything with no special meaning stands for itself. | cat |
. | Any character except a line break. | c.t |
[a-z] | A character class: one character from the set. Ranges and literals can be mixed. | [A-Fa-f0-9] |
[^a-z] | A negated class: one character that is not in the set. | [^0-9] |
\d \D | A digit, or anything that is not a digit. | \d\d:\d\d |
\w \W | A word character (letter, digit or underscore), or anything else. | \w+ |
\s \S | Whitespace, or anything that is not whitespace. | \S+\s\S+ |
\n \t \xNN | Control characters and hex escapes. | \x41 |
\. | A backslash makes the next character literal. | \$\d+ |
ab | Concatenation. Two expressions in a row, matched in order. | ab |
a|b | Alternation. Either side, drawn as a fork of two empty moves. | cat|dog |
( ) | A group. The machine treats it as brackets only: capture is not modelled. | (ab)c |
(?: ) | A non-capturing group. Identical to the above as far as the machine is concerned. | (?:ab)c |
(?<n> ) | A named group. Also treated as brackets only. | (?<year>\d{4}) |
* | Zero or more. Drawn as a split state with an arrow back into its own body. | ab* |
+ | One or more. The body is entered once, then the loop is optional. | ab+ |
? | Zero or one. A split state that either enters the body or steps over it. | ab? |
{n} | Exactly n. The body is copied n times, so the state count grows with n. | \d{4} |
{n,} | At least n. Copied n times with the last copy looping. | \d{2,} |
{n,m} | Between n and m. n copies, then m minus n optional copies. | \d{2,4} |
^ $ | Anchors. They consume nothing and only pass at the start or end of the input. | ^ab$ |
*? +? ?? | Lazy quantifiers are accepted and then ignored, because laziness changes which match is reported and not which strings match. | a+? |
What it refuses, and why the refusal is the honest answer
| Syntax | Why not | Example |
|---|---|---|
\1 \2 | Backreferences. A machine whose only memory is its current state cannot remember what a group captured. This is not a simplification, it is a proof. | (\w)\1 |
(?= ) (?! ) | Lookahead. A condition on text the machine has not read yet, which is not a move from one state to another. | a(?=b) |
(?<= ) (?<! ) | Lookbehind. Same problem, pointing the other way. | (?<=a)b |
\b \B | Word boundaries. They test the two characters either side of a position rather than consuming one, so there is no arrow to draw. | \bcat\b |
Every one of these four is a zero-width or a memory-carrying construct. They are perfectly ordinary in a regex engine and they have no representation as an arrow between two states, so drawing something approximate would teach the wrong thing about what a state machine can do.
How a pattern becomes a machine
A regular expression is a program, and like any program it gets compiled before it runs. This page stops at the first stage of that compilation and draws the result.
There are three steps. First the pattern is parsed into a tree: characters and classes at the leaves, and concatenation, alternation and the quantifiers as the nodes above them. Then that tree is turned into a state machine by Thompson construction, published by Ken Thompson in 1968 and still the standard way to do it. Each kind of tree node has a small fixed shape it becomes, and the shapes are glued together in the same arrangement as the tree. Finally the machine is run against your test string.
The gluing is done with empty moves, drawn here as dashed arrows: transitions the machine can take without reading any input. They exist so the gadgets fit together without knowing anything about each other, and they are the reason a small pattern produces more states than you might expect. They are also the interesting part of the picture. A fork of two dashed arrows is a choice the machine has not made yet, and a dashed arrow pointing backwards is a loop.
A worked example
Take ^(ab)*c?$, which is one of the starter patterns. Reading it left to right: the machine begins with a dotted arrow for ^, which consumes nothing but only passes at position zero.
Then (ab)*. The group is transparent to the machine, so this is a star over the two-character sequence ab. A star becomes one split state with two empty moves out of it: one into the body, one straight past it. The end of the body loops back to that same split state, which is why the diagram has an arrow travelling right to left. Every time the machine arrives back at the split it faces the same choice again, and because it is non-deterministic it takes both.
Then c?, another split, this time with no loop: either read a c or step over it. Finally $, a second dotted arrow that only passes at the end of the input, and then the accepting state drawn as a double circle.
Step the string ababc through it and watch the live set. After two characters the machine is in several states at once, because having just finished one ab it is simultaneously about to start another and about to give up on the loop and look for a c. It does not decide. It carries both possibilities forward and lets the input settle the question, and that is the difference between this and the engine in your language.
Where the picture stops being true
This is the part worth reading, because a diagram is persuasive and this one is only telling you about half of what your regex engine does.
Your language does not run this machine. JavaScript, Python, Java, Ruby, PHP and Perl all use backtracking engines. A backtracking engine walks the parse tree directly, tries one alternative at a time, and unwinds when it fails. Go's regexp package, RE2 and rust's regex crate are the well-known exceptions and are closer to what is drawn here.
That difference is visible in the results. This machine reports the leftmost-longest match, because it has no reason to prefer one branch over another. A backtracking engine reports the leftmost-first match, in the order the alternatives were written. Against ab, the pattern a|ab matches ab here and a in your editor.
It also means the diagram cannot warn you about the failure mode people actually hit. Catastrophic backtracking is a property of the algorithm, not of the language the pattern describes, so a pattern that would hang a server for minutes runs here in linear time and draws a perfectly ordinary picture.
Captures are not modelled. A group is treated as brackets. The machine knows whether a string matched, not which part of it a group was sitting on, because remembering that would require memory a finite state machine does not have. For the same reason lazy quantifiers are accepted and then ignored: laziness picks between several matches, and this machine only answers whether there is one.
Positions are UTF-16 code units. The test string is walked the way a JavaScript regex without the u flag walks it, so a character outside the basic multilingual plane counts as two positions. That is a real property of most engines rather than a shortcut, but it will surprise you if you paste an emoji in.
Terminology
- State
- One of the finitely many situations the machine can be in. A circle in the diagram, numbered so the step readout can name it.
- Transition
- A labelled arrow. Solid arrows read one character, and the label is the slice of your pattern that produced them.
- Empty move
- An epsilon transition. A dashed arrow the machine can follow without reading anything.
- NFA
- Non-deterministic finite automaton. The machine drawn here: it can be in several states at once, and it explores every possibility in parallel rather than choosing.
- Live set
- All the states the machine could be in after reading a given number of characters. The step readout prints them by number.
- Accepting state
- The double circle. If it is live when the input runs out, the string matched.
- Thompson construction
- The algorithm that turns each regex operator into a small fixed fragment of states, then joins the fragments with empty moves.
- Leftmost-longest
- The POSIX rule for reporting a match, and the one used here. A backtracking engine uses leftmost-first instead.
Common questions
What is a regex state machine?
It is the thing a regular expression actually is, underneath the notation. A finite state machine is a set of states and a set of labelled transitions between them. You start in one state, read the input one character at a time, and follow whichever transition is labelled with the character you just read. If you are in an accepting state when the input runs out, the string matched.
The diagram on this page is a non-deterministic finite automaton, or NFA. Non-deterministic means a state can have several transitions for the same character, plus transitions that move without reading anything at all. Rather than guessing which to take, the machine takes all of them at once, which is why the tool highlights a set of live states rather than a single dot.
Why an NFA and not a DFA?
Because the NFA is the one that looks like the pattern you typed. Thompson construction maps each piece of syntax onto a small fixed gadget: alternation becomes a fork, a star becomes a loop, a literal becomes one arrow. You can put your finger on a state and say which character of the pattern produced it, which is the whole point of drawing it.
A DFA is the same language with the ambiguity compiled out. It runs faster and it is usually smaller to store, but the correspondence with the source is gone: one DFA state is a whole set of NFA states, and the loops and forks you wrote have been dissolved into a transition table. It is the better machine and the worse picture.
Why does this tool report a different match from my language?
Most likely because of leftmost-longest versus leftmost-first. Load the greedy trap example: the pattern a|ab against the string ab. This tool reports a match of ab. JavaScript, Python, Java, PCRE and Perl all report a match of a.
Neither is wrong. An NFA explores both branches simultaneously and there is no reason for it to prefer one over the other, so the convention is to report the longest match, which is what POSIX specifies. A backtracking engine tries the alternatives in the order you wrote them and stops at the first one that succeeds, so a wins because it is on the left. If the order of your alternatives matters to the result, you are relying on backtracking behaviour that this diagram deliberately does not model.
Will this show me catastrophic backtracking?
No, and it cannot. Catastrophic backtracking, the failure behind most ReDoS reports, is a property of the backtracking algorithm, not of the pattern's language. A pattern such as (a+)+b makes a backtracking engine try an exponential number of ways to divide the a's between the inner and the outer group before it gives up.
Simulate that same pattern as an NFA and nothing dramatic happens: the set of live states is bounded by the number of states in the machine, so the run is linear in the length of the input no matter how the pattern is written. The diagram will look completely calm for a pattern that would hang a production server. Use a dedicated ReDoS checker for that question.
Why will it not accept a backreference?
Because no finite state machine can express one. A backreference such as (\w)\1 requires the machine to remember which character the group captured, and the only memory a finite state machine has is which of its finitely many states it is currently in. A pattern with a backreference is not a regular language, which is a theorem rather than a limitation of this tool.
This is the one case where the tool refuses instead of approximating. Every other unsupported construct could be drawn wrongly and look plausible; a backreference could not be drawn at all, so the error says exactly that.
What do the dashed arrows mean?
They are empty moves, usually written with the Greek letter epsilon. The machine changes state without reading a character. They are how Thompson construction glues gadgets together: a fork for alternation is one state with two empty moves out of it, and a loop for * is an empty move back to the start of the body.
Dotted arrows are different again. Those are the anchors ^ and $, which also consume nothing but only pass at one specific position in the input. Solid arrows are the only ones that read a character, and they are labelled with the exact slice of your pattern that produced them.
Why does it refuse a large repeat count like {200}?
Because this tool builds the machine by copying. \d{200} means two hundred copies of the digit gadget, and the diagram would be two hundred identical circles in a row: technically correct, completely useless to look at, and slow to lay out. The limit is 64.
A real engine does not copy. It keeps a counter and reuses the same states, which is why {200} costs it nothing. That difference is worth knowing about, because the counter is also the reason a bounded repeat can interact badly with backtracking in ways the unbounded * does not.
Does anything get sent to a server?
No. The parser, the construction, the layout and the simulation all run in your browser as ordinary JavaScript. Nothing is uploaded, nothing is stored, and the page works offline once it has loaded.
The one thing that leaves the page is the address bar: the pattern and the test string are written into the query string so a link can be shared. That is a local change to your own history and it is only visible to whoever you send the link to.
Where this comes from
The construction is Ken Thompson's, from “Programming Techniques: Regular Expression Search Algorithm”, Communications of the ACM 11 (6), June 1968. The simulation strategy, tracking a set of live states rather than backtracking, is the same paper's, and Russ Cox's Regular Expression Matching Can Be Simple And Fast is the clearest modern write-up of both, including the leftmost-longest and catastrophic backtracking differences described above.
The syntax accepted here is a subset of the JavaScript regular expression grammar as specified in ECMA-262. Where this tool and a JavaScript engine differ in behaviour rather than in syntax, the difference is named on this page rather than smoothed over.
The parser, the construction and the simulation are all this tool's own, written for this page, with no regex library involved: using one would have meant drawing a diagram of a machine that was never actually built. If you find a pattern this accepts and draws wrongly, tell me and it gets fixed.