Automata Behind Regular Expressions

You write a pattern, you hand it to a library, and a moment later you have your matches back. I have used regular expressions almost every working day for years, and for most of that time I had no picture at all of what happens in between. It turns out to be something small and completely concrete. So that is the question for the next twenty minutes. What actually runs when a regular expression matches a string? We are going to build one of these machines by hand, feed a string through it, watch it turn into a faster machine, and then find two things it flatly cannot do. Start as small as anything can be. Here is the pattern a b. One a, then one b, and nothing else. And here is its machine. Three circles. They are called states, and the machine is sitting in exactly one of them at any moment. The little arrow on the left marks where it starts, so before it reads anything it is in q nought. The arrows between the circles are transitions, and each one carries a character. This one says: if you are in q nought and the next character is an a, move to q one. This one says: from q one, a b takes you to q two. And that second circle drawn around q two is the whole point of the picture. It means accepting. If the string runs out while the machine is sitting there, the pattern matched. If it runs out anywhere else, it did not. So feed it the string a b. We begin in q nought. The first character is an a, so we follow the a arrow and land on q one. The next character is a b, which carries us to q two. The string has run out and we are sitting in the accepting state, so this one matched. Two characters, two arrows, no searching and no going back. Now feed it a a instead. The first a is fine and puts us in q one. Then the second a arrives, and there is no arrow out of q one labelled a. The machine has nowhere to go, so it stops, and it reports no match. That is the whole vocabulary. States, transitions, one place to start, and one or more accepting states. Everything for the rest of this lecture is that same picture with more arrows on it.

Here is the thing nobody tells you. The machine is not guessed at, it is computed, and it follows the shape of the expression. There are only four kinds of piece in a basic regular expression, and each one has its own translation. A single character is one arrow between two states. That is rule one and that is the whole of it. A choice, written a bar b, is two arrows leaving the same state, one for each alternative. Whichever character actually turns up, one of those arrows is available to take. A star means any number of repetitions, including none at all, and that is an arrow that comes straight back to the state it left. Go round it as often as you like, or never. And concatenation, writing one piece after another, glues the end of the first onto the start of the second. Four rules, and between them they translate anything built from characters, choice, star and concatenation. One honest note before we use them. The textbook construction bolts a couple of extra bookkeeping states onto every single piece, so the drawing gets enormous very fast. I am going to draw the tidied result instead. It accepts exactly the same strings, and you can actually see it. Now a pattern you might genuinely write. Bracket, a bar b, close bracket, star, then a b b. In words: any number of a's and b's, and then the string has to finish with the letters a, b, b. Take the star first. Rule two says the choice inside it is two arrows off one state, and rule three says the star sends them back where they came from. So both arrows leave q nought and both return to q nought, and I have drawn them as one loop carrying two labels. Read that loop as: sit here and swallow whatever you like. Now rule four, concatenation, glues the rest of the pattern onto the end of it. The rest is three plain characters, so rule one gives us three arrows in a row. An a takes us from q nought to q one. A b takes us on to q two. And a final b takes us to q three. And q three is the accepting state, because arriving there is exactly what it means to have finished with a b b. Four states, five arrows, and every one of them came off a rule. Now look hard at q nought, because there is something wrong with it. Two different arrows leave that state carrying the letter a. One is the loop and one goes to q one. So when an a arrives, the machine has no way to decide. Is this a in the middle of the string, or is it the a that starts the ending we are looking for? It cannot know until it has read what comes after. That is what nondeterministic means. The fix is not to decide. Here is an input string, a a b b, and here is the list of states the machine could possibly be in. Before we read anything that list has exactly one entry, q nought. Read the first a. From q nought, two arrows are labelled a: the loop, which keeps us where we are, and the one across to q one. We refuse to choose, so we take both. The machine is now in q nought and q one at the same time. Read the second a. From q nought we get q nought and q one all over again. From q one there is no a arrow at all, so that possibility simply dies. The set has not changed, but the q one in it is a brand new thread, not the old one. Read a b. The loop keeps q nought alive, and from q one the b arrow moves us on to q two. So the live set is now q nought and q two, and the thread that was in q one has moved along with it. Suppose the string stopped right here, at a a b. We would be holding q nought and q two, and neither of those is an accepting state. So that string does not match, and we can say so without trying anything else. But it does not stop. Read the last b. The loop keeps q nought once more, and from q two the b arrow carries us into q three. Now the string has run out and one of the states we are holding is accepting, so the pattern matched. And that is the rule in general. If any possibility in your live set is an accepting state, it is a match. Notice what we never had to do. We never backed up and tried a different route through the pattern. We carried every possibility forward together and we read each character exactly once. Nondeterministic does not mean guessing. It means holding several answers at the same time.

That machine works, and it is honest about not knowing. But look at what it costs. On every character we had to take a whole set of states, follow every arrow out of every one of them, and build the next set. So here is the idea that fixes it, and it is almost embarrassingly simple. Those sets are the only thing that ever mattered. So make each set a state in its own right. Then the new machine has no choices left in it anywhere. One state, one character, one next state. That is what deterministic means, and it is why the second machine can be a table you index into. First write down the old machine as a table, straight off the diagram. From q nought an a goes to q nought and q one, and a b goes back to q nought. From q one, an a goes nowhere and a b goes to q two. From q two, a b goes to q three. And q three has no arrows out of it at all. Now start the new machine from the only set we know, the one we begin in. Just q nought. Call it A. From A on an a, the table says q nought and q one. That is a set we have not met before, so it earns a name of its own. Call it B. From A on a b, we get just q nought again, which is A itself. Now do B, which is q nought and q one. On an a, q nought gives q nought and q one, and q one gives nothing. So we land back on B. On a b, q nought gives q nought and q one gives q two, so we get q nought and q two. New set. Call it C. Then C, which is q nought and q two. On an a we get q nought and q one, which is B again. On a b, q two gives q three, so we get q nought and q three. One more new set. Call it D. And finally D, which is q nought and q three. On an a we get B. On a b, q three gives nothing, so we get plain q nought, which is A. And that is the moment the whole thing stops. Every set we reached was already on the list. Four sets, and the search has nothing left to find. So draw them. Four states, A, B, C and D, and now every state has exactly one arrow leaving it for a and exactly one for b. From A an a goes to B, and a b comes straight back to A. From B an a stays on B, and a b drops down to C. From C an a climbs back to B, and a b carries on to D. And from D an a cuts across to B, while a b returns to A. Which one accepts? D does, and for one reason only. D is the set that contains q three, and q three was the accepting state of the old machine. That is the whole rule: a set accepts when anything in it accepts. And now run a a b b through this one. We start in A. The first a takes us to B. The second a keeps us there. Then a b drops us down to C, and the final b carries us into D. One state at every moment. No sets, no threads, and a single table lookup for each character. That is about as fast as a matcher can be, and it does not care how complicated the pattern was. There is a catch, though, and it is a big one.

Here is a pattern that looks completely harmless. Any number of a's and b's, then an a, then any two characters. Read in plain English, it says the third character from the end is an a. Translate it with the same four rules and you get four states. A loop that swallows anything, an a that commits, and then two arrows that will take whatever they are given. That is a small machine, and simulating it with a live set is cheap. At most four states are ever alive at once. Now determinise it and watch what happens. The deterministic machine is not allowed to hold possibilities. When an a arrives it has to commit right then to whether this is the a we are looking for. But it cannot know that, because the answer depends on how many characters come afterwards. So it does the only thing left. It remembers the last three characters it has seen, and when the input finally ends it looks at the oldest of the three. How many things is that to remember? Two possibilities for each of three positions. Two times two times two. Eight states, where the nondeterministic machine had four. Now replace the three with an n. The nondeterministic machine grows very gently: it needs n plus one states, one for each position it still has to watch go by. That is the green line. The deterministic one has to remember the last n characters, and the number of things it might need to remember is two to the n. That is the red one. At n equals three the two are still close. Push it to five and the gap has opened. Push it to eight and the red curve has left the picture behind entirely, while the green one has crawled up to nine. Put some numbers on it. With n of ten, eleven states have become one thousand and twenty four. Push n up to twenty and those twenty one states have become the figure on the bottom row, which is over a million. And nobody has done anything wrong here. This is not a bug in an implementation. It is the price of removing the choices. The choices were carrying information, and if you refuse to defer them, you have to store that information as states instead. Which is why serious engines mostly do not build the whole deterministic machine up front. Some simulate the nondeterministic one directly, carrying the live set exactly as we did by hand a few minutes ago. Others build deterministic states lazily. They construct a state the first time some input actually reaches it, cache it, and throw the cache away when it grows too large. You pay for the states your data really visits and not for the ones it never does.

One last limit, and this one is not about size. It is about something a regular expression cannot do at all, no matter how long you are willing to make it. Here is the language. Some number of opening brackets, followed by exactly the same number of closing brackets, and nothing else. Two open and two closed is in. Three and three is in. Two open and one closed is not. Everybody's first instinct is to reach for a star. There is no pattern that does it, and I want to show you why on the actual machine, because the argument is short and it is completely concrete. Suppose there were such a pattern. Then there is a machine for it, and that machine has some fixed number of states. It does not matter what the number is, so let us say four. Now feed it four opening brackets and nothing else yet. It starts somewhere, and each bracket moves it along, so we can watch the states it visits. Count the visits. Where it was before any bracket, then after one, after two, after three, after four. That is five visits, and I have written the count above each one. Five visits, and the machine only has four states to be in. So two of these five have to be the very same state. There is nowhere else for them to be. That is the whole of the argument, and it is just counting. Say it is this one and this one. Then they are not two states, they are one state that the machine passed through twice. Give it a name, q. And now look at what sits between them. The machine left q, read two opening brackets, and arrived back at q. That is a loop, and the machine has no way of knowing it went round it. So send it round twice. It reads two more opening brackets, comes back to q again, and it is in precisely the state it would have been in anyway. Then the four closing brackets do exactly what they did before, and it accepts. But count the string it has just accepted. Six opening brackets, and still only four closing ones. The machine has accepted something that is not balanced, which is the one thing we assumed it never did. And the four was arbitrary. Whatever number of states you name, I feed it that many opening brackets, count one more visit than it has states, and find the same loop. Every fixed number loses. So what actually went wrong? Not the star, and not the choice. The machine ran out of memory. To match brackets you have to remember how many are still open, and that number has no ceiling. A machine with a fixed number of states can remember a fixed number of things. That is the real boundary, and every language that needs to count without limit sits on the far side of it. Which is why the recursion and the backreferences in your favourite engine are not regular expressions in this sense at all. They are the features that step outside, and the price of stepping outside is that they can no longer be run as a finite machine. So that is the whole picture. Your pattern becomes a machine, one arrow per character, one state at a time. Nondeterminism means holding several possibilities together rather than guessing. Determinising trades those possibilities for states, sometimes at a terrible price. And a machine with a fixed number of states can only ever remember a fixed amount. Next time a pattern is slow, or refuses to do what you want at all, you now know which of those four facts you are standing on.