An ELI5 version of REGEX and NFA

Regex engines often talk about NFAs: nondeterministic finite automata. That name is a mouthful, so here is the plain idea. An NFA is a little machine with a finite set of states. It reads input one character at a time and moves from state to state. “Nondeterministic” means that at some points more than one move is legal, or a move can fail and the machine still has other attempts to try. A lot of how a regex “tries” a pattern against a string is that kind of walk: advance when a piece matches, and when it does not, back up and try from another place.

The rest of this piece is one concrete, slightly silly picture of that walk.

The Automaton

You have a robot (our automaton) that walks the REGEX dungeon door by door. Each door is one piece of the pattern. The string is the belt of keys the robot carries, used in order, one character at a time.

To open the next door, the robot must spend the next key (or keys) that that door accepts. If it reaches the last door and gets through, the pattern matches. If it hits a key that cannot open the current door, it fails that attempt: it is sent back to the first door of the pattern and starts again from the next character in the string. Progress on the previous attempt does not carry over.

So with the string "budega", if an attempt fails on "b", the next attempt starts with "udega".

Literal doors

For the dungeon /there/, there are five doors in a row: t, h, e, r, e. Each needs exactly that key, in that order.

• "there" works. The robot uses every key and exits the dungeon.
• "here" never opens the first door. It tries "here", then "ere", then "re", then "e", and leaves sad.
• "then go over there" looks promising at first. The robot opens t, h, e, then stalls on "n" because the next door wants r. That attempt dies. It restarts from "hen go over there", fails the first door over and over, until it finally tries from "there" and gets through.

Doors that accept more than one key shape

Some doors take a choice of characters (ranges) or a flexible count (quantifiers).

In /[hm]el+ow?/, the five doors are: [hm], e, l+, o, and w?.

• "hello" matches. The first door accepts h or m. The l+ door takes both ls. The o door takes o. The last door w? accepts zero or one w; here it takes zero and the robot still passes.
• "mellow" matches for the same reasons. At w? the robot spends its one w and walks out.

I had a lot of fun painting this in bright colors. I hope the map still helps when the metaphor gets loud.