TM·IX Limits of computation Chapter 54 of 65

Automata and regular expressions

A machine that has nothing but a finite number of states. It checks phone numbers, searches gigabytes of logs and stands behind every regular expression. The chapter is a book of puzzles: crosswords made of regexes, a turnstile, an automaton built from a formula. It ends with the post-mortem of an outage in which one regex knocked out the websites behind Cloudflare worldwide for 27 minutes on July 2, 2019.

University 75 minutes Theory of computation Practice History

TM·IX

Limits of computation

Builds on: 07 · A conversation made of strings 19 · Six handshakes

What you will take away

write regular expressions that validate and search text (classes, repetition, groups, anchors) and use Python’s re module
build a finite automaton that validates input, and turn a nondeterministic automaton into a deterministic one
spot regexes prone to catastrophic backtracking and rewrite them safely
prove with the pumping lemma that a job is beyond any finite automaton

The last chapter ended with a question: is there a program that can check any program for infinite loops? To answer it, we have to pin down what a machine is, and the place to start is the simplest one. The simplest machine remembers a single thing: which state it is in. It has finitely many states, and each input symbol moves it from one state to another according to a table. We have met this machine three times already: the traffic light in Chapter 31, the KMP algorithm in Chapter 27, the lexer in Chapter 50. Time to study the machine itself: what it can do and what it can’t.

As it turns out, it can do what regular expressions can do, no more and no less. Those are the short formulas, like \d{2}/\d{2}/\d{4}, that people use every day to validate input, search logs and clean up data. So the chapter is a book of puzzles: first crosswords whose clues are regexes, then automata you build yourself. And at the end, the post-mortem of an outage in which one eleven-character regex stopped a sizable part of the internet for 27 minutes.

The first crossword

The rules are simple. Put one letter in each cell. Each row, read left to right, must match its regular expression in full, and each column, read top to bottom, must match the expression of its column. A regular expression is a pattern: a letter stands for itself, and a few symbols control choice and repetition.

Notation	Meaning	Example
`C`	the letter C	`CAT` matches only “CAT”
`.`	any character	`C.T`: CAT, COT, C5T
`[CH]`	one of the listed characters	`[CH]AT`: CAT, HAT
`[^H]`	any character except the listed ones	`[^H]AT`: CAT, BAT, but not HAT
`A\|B`	either A or B	`YES\|NO`
`X?`, `X*`, `X+`	X zero times or once, any number of times, at least once	`BO*K`: BK, BOK, BOOK
`(…)`	a group: repetition and “or” apply to all of it	`(HA)+`: HA, HAHA

A crossword made of regular expressions. The expressions for the rows and columns are under the grid; a green check means a row or column matches its expression, a red cross means it is filled in but doesn’t match. Each crossword has a single solution. Start with the cells where you have the fewest choices.

While solving, you most likely worked like a machine: you read an expression from left to right and asked of every cell what could go there, keeping in mind only where in the expression you were. That is how a finite automaton works too, and it deserves a closer look.

A machine without memory

Take a subway turnstile. It can be in one of two states: locked or unlocked. There are two events as well: someone drops in a coin, or someone pushes. A locked turnstile is unlocked by a coin, and a push changes nothing. An unlocked one lets a person through on a push and locks again, while a second coin is wasted. The whole logic of the turnstile is a table of four rows.

The turnstile doesn’t care how many people went through today or how many coins were wasted: all of its past is squeezed into one word, “locked” or “unlocked.” In Chapter 31 we called such a device a finite-state machine. Now for a proper description. A deterministic finite automaton, or DFA, consists of five things: a finite set of states; an alphabet, the symbols it reads; a transition table, which names the next state for a given state and symbol; a start state; and a set of accepting states. The automaton reads a string symbol by symbol, moving through the table, and when the string runs out, it accepts the string if it has landed in an accepting state and rejects it otherwise. “Deterministic” means there is never a choice: the state and the symbol fix the next step uniquely.

The set of all strings an automaton accepts is called its language. If “unlocked” is the accepting state, the language of the turnstile is every sequence of events after which you can walk through. Here is a more interesting automaton: it reads the binary representation of a number, one digit at a time, and tells whether the number is divisible by three.

The number $2^{64} + 2$ takes 65 binary digits, and the automaton gets by with three states. It doesn’t remember the number, only the remainder of the part read so far divided by 3. Appending a binary digit b on the right multiplies the number by 2 and adds b, and the remainder of the result depends only on the old remainder: $(2r + b) \bmod 3$. It is the same idea as in KMP: remember one small number about everything you have read, and that memory is enough for a text of any length.

Build some automata yourself. The editor below already holds the turnstile and the divisibility-by-three automaton, plus a few tasks.

The automaton editor. “+ state” adds a circle, which you can drag with a finger or a mouse. Tap a state to select it, and the buttons “start,” “accepting,” “transition” and “delete” appear. To add a transition, tap “transition,” then the state it leads to, and type its symbols (separated by commas; 0-9 means all digits). Tap a transition’s label to change or erase it. At the bottom is a string to test: “step” reads one symbol, “to the end” reads the whole string. In the tasks, the automaton is checked against a set of strings.

Validating input

The most common job of a finite automaton in an ordinary program is to check that a person typed something correctly. Take a decimal number as people write it in a form: an optional minus, digits, and then perhaps a point and more digits. -12.5, 7, 0.25 pass; 12., .5, --3, 1.2.3 don’t. The automaton for this needs five states: “nothing read yet,” “read a minus,” “digits of the integer part,” “read the point,” “digits of the fractional part.” Two of them are accepting, the ones where a number may end.

The automaton and the one-liner -?[0-9]+(\.[0-9]+)? agree on all eight strings, and that is no accident. Read the expression through the automaton’s eyes: -? says the start may move on a minus or may not; [0-9]+ is a digit followed by a loop on digits; (\.[0-9]+)? is an optional tail: a point, a digit, a loop. The backslash before the point is needed because a bare point means “any character.” The function re.fullmatch from the re module checks whether the whole string matches the expression.

Nerve nets and regular events

Regular expressions were invented by a logician, and he invented them while studying a model of the nervous system. In 1943 Warren McCulloch and Walter Pitts described a simplified model of a neuron: a cell that fires when enough of its inputs have fired. Such cells can be wired into networks, and the question was what a network like that is able to recognize.

In the summer of 1951, at the RAND Corporation in Santa Monica, Stephen Cole Kleene took up the question; he was a student of Alonzo Church, whom we will meet in the next chapter. In a report called Representation of Events in Nerve Nets and Finite Automata he described which sequences of signals a network with a finite number of cells can tell apart from all the others. He called them regular events and invented a notation for them with three operations: one thing followed by another, “or,” and repetition any number of times. Repetition is still written with an asterisk and called the Kleene star. The report was published in 1956 in Automata Studies, a volume edited by Claude Shannon and John McCarthy.

Kleene’s main result is a bridge between formulas and machines. The languages accepted by finite automata are called regular, and Kleene’s notation is called regular expressions.

A set of strings can be described by a regular expression if and only if some finite automaton accepts it.

In one direction, from an expression to an automaton, the construction goes piece by piece through the expression, like the parser of Chapter 50. It helps to allow transitions that read no symbol at all; they are labeled with the letter ε. To each piece of the expression we assign an automaton with one entrance and one exit. A symbol becomes two states and an arrow labeled with that symbol. A sequence AB: an ε-arrow joins the exit of the automaton for A to the entrance of the automaton for B. An “or” A|B: a new entrance with ε-arrows into both automata, and a new exit that ε-arrows from both lead into. A star A*: an ε-arrow from the exit of A back to its entrance, to repeat, and an ε-arrow from a new entrance straight to a new exit, to repeat zero times. These four parts build an automaton for any expression, and it has at most twice as many states as the expression has characters. The next section shows how to get rid of the ε-arrows.

In the other direction, from an automaton to an expression, states are removed one at a time, and every route that went through a removed state becomes an arrow labeled with a whole expression: if the way from p to q went through r, which had a loop, the new arrow from p to q is labeled “the way into r, the loop any number of times, the way out of r.” When only the start and the accepting state are left, the label of the arrow between them is the expression we want.

The theorem gives a practical rule: anything a regular expression checks without special extras can be checked while remembering a finite amount of information, and the other way around. Phone numbers, dates, ZIP codes and numbers all form regular languages. Balanced parentheses are not, and at the end of the chapter we will prove it.

The machine that guesses

A strange automaton turned up in the proof: it has ε-arrows, and several arrows with the same symbol may leave one state. The easiest way to picture it at work is to pretend that it guesses: at every fork it takes the right road, if there is one. A string is accepted if at least one path leads to an accepting state. Such an automaton is called nondeterministic, an NFA for short.

Machines can’t guess, but guessing can be replaced by trying everything: follow all the options at once. Instead of one current state, keep the set of all the states where the automaton could be. Each symbol takes one set to another. Here is an example where an NFA is much simpler than a DFA: strings of zeros and ones whose third symbol from the end is a one. The NFA reads the string, and on some 1 it “decides” that this one is third from the end; then it checks that exactly two symbols follow.

In 0100 the third symbol from the end is a one, and at the end the set contains the accepting state 3; in 0011 that symbol is a zero, and state 3 is missing from the set. The “guessing” hides in the set of states: the machine follows every guess at once. The method Ken Thompson described in 1968 searches text the same way, and its time grows linearly with the length of the text: one step over the set for each symbol.

But a set of NFA states is itself a state, and there are only finitely many such sets. So we can build a DFA in advance in which every state is a set of NFA states. Start with the set where the NFA can be at the beginning, and for every symbol compute where the set goes; each new set becomes a new DFA state, and we do the same for it. This is the breadth-first search from Chapter 19, only the vertices of the graph are sets. The technique is called the subset construction. Michael Rabin and Dana Scott proposed it in 1959, in the paper that earned them both the Turing Award in 1976. It shows that guessing adds no power: anything an NFA accepts is accepted by some DFA too.

From a regex to an NFA and then to a DFA. Type an expression (letters, digits, |, *, +, ?, parentheses) or pick a preset. At the top is Thompson’s automaton, assembled from the parts used in the proof; the ε-arrows are dashed. Below it is the subset construction, step by step: each row of the table is a new DFA state, that is, a set of NFA states. At the bottom is the resulting DFA. The test string lights up its path in both automata.

Determinism is paid for in size. The NFA for “the third symbol from the end” has four states, while a DFA has to remember all of the last three symbols; otherwise, once the string ends, it can’t know what the third from the end was. Here is how the DFA grows if we ask about the $n$th symbol from the end.

Each extra position doubles the DFA: $2^n$ states against $n + 1$. Fewer won’t do: a DFA must tell apart all $2^n$ possible endings of the string, because for any two endings there is a continuation after which one says “yes” and the other “no.” So search programs have to choose between two roads. They can build the DFA in advance and then read the text at full speed, at the risk of a blow-up in size; or they can track the set of NFA states on the fly, slower per symbol but with no blow-up. There is a middle road too: build DFA states lazily, only the ones the text reaches. That is how Google’s RE2 and Rust’s regex library work, for example.

Thompson, QED and grep

Regular expressions were carried from theory into programs by Ken Thompson, one of the future authors of Unix (Chapter 33). He wrote his own version of the QED text editor for the CTSS time-sharing system on an IBM 7094 and gave it search by patterns in Kleene’s notation. In June 1968 Communications of the ACM published his four-page paper, Regular Expression Search Algorithm. Thompson built an NFA from the expression and tracked the set of its states along the text, as we did above. And instead of interpreting the automaton, he translated the expression into IBM 7094 machine code while the program ran: one of the first examples of the just-in-time compilation from Chapter 52.

Five years later, by then in Unix, Doug McIlroy, the man behind pipes (Chapter 36), asked Thompson for a program that would find the lines matching a pattern anywhere in a file. The editor ed could do it, but it loaded the whole file into memory, and files could be big: Lee McMahon, from the same lab, was analyzing the text of the Federalist Papers to work out who had written which of them. Thompson said he would think about it overnight and brought the finished program the next morning. Many years later, in a 2019 conversation with Brian Kernighan, he admitted that he had already had the program, written for himself, and had spent about an hour that evening fixing its bugs. The name came from the ed command g/re/p: globally, by regular expression, print. grep went into the Fourth Edition of Unix, released in November 1973.

Since then regular expressions have settled almost everywhere: in grep and sed, in code editors, in languages from Perl and JavaScript to Python, in databases and in firewall rules. But along the way their paths parted. Alfred Aho’s egrep, which went into the Seventh Edition of Unix in 1979, built a DFA, as in the subset construction. In 1986 Henry Spencer released a free regex library that worked differently, by backtracking; Perl’s regular expressions grew out of it, and the regular expressions of most languages, Python’s among them, followed Perl’s example. Why it worked differently, and how that ended, is the story at the end of the chapter. First we need to learn to use what we have.

Regexes in Python

In Python, regular expressions live in the re module. You write an expression in a “raw” string r"…", where a backslash stays a backslash instead of turning into a string escape like \n. Besides the notation from the crossword you will need a few more pieces. \d is a digit, \w a letter, digit or underscore, \s a whitespace character. {n} and {n,m} repeat exactly $n$ times or from $n$ to $m$ times. ^ and $ are the start and the end of the string, \b a word boundary. There are four main functions: re.fullmatch checks the whole string, re.search finds the first occurrence, re.findall finds all of them, re.sub replaces what it finds. Parentheses also remember what they grouped: whatever matched a group can be pulled out afterward.

The year mentioned most often in the novel is 1812, followed by 1805: the years of the two wars between which the story unfolds. re.finditer hands out matches one at a time, together with their groups, and (?P<name>…) gives a group a name to fetch it by. The named groups caught “18th Brumaire”: Brumaire is a month of the French revolutionary calendar, and the pattern takes any word after the number without knowing what a month is. In rf"…" the expression is assembled by an f-string, so the curly braces of the repeat had to be doubled. And one last rule that saves hours: re.search looks for the pattern anywhere in the string, so validating input calls for re.fullmatch; otherwise \d+ will “confirm” that abc5 is a number.

Now for harder crosswords: they have repetition and one new piece of notation, explained right after them.

The second round of crosswords. The last one uses \1, “the same text that the first group matched”: (.)O\1 matches POP but not POT.

A step beyond the automaton

The notation \1 is called a backreference: it demands that the text the first group matched appear again. With it, doubled words are easy to find, among them a common typo like “the the” or “is is.” In War and Peace the doubling is mostly deliberate: that is how the characters talk.

“Yes, yes” leads the list, and the regex also catches grammar that only looks like a typo: “had had” and “that that” are perfectly good English. The notation is handy, but it comes at a price, and a fundamental one. The language “a word repeated twice” is not regular: to check that the second half matches the first, you have to remember the whole first half, and it can be as long as you like. A finite automaton can’t do that; for a similar case we will prove it in the section on pumping. So Python’s regular expressions are stronger than Kleene’s, and no finite automaton can stand behind them.

Backtracking

The regex engines of Python, Perl, Java and JavaScript don’t build an automaton. They try. Faced with a choice (how many characters to give to x+, which branch of | to take), the engine takes the first option and moves on. If something fails further along, it goes back to the last choice and tries the next option. It is a depth-first search over a tree of options, like the maze walk in Chapter 19 or the exhaustive search of Chapter 9. Usually the tree is small, and everything is fast. But some expressions have exponentially many ways to cut up a string, and when there is no match, the engine will try every last one of them.

Every two extra characters make it four times slower: the time doubles with each character. A string of $n$ x’s can be cut into nonempty pieces in about $2^n$ ways, and for each way the engine checks whether a y stands at the end. At this rate a string of forty x’s would take many hours. The phenomenon is called catastrophic backtracking, and an attack that feeds such strings to a server is called ReDoS, regular expression denial of service. Thompson’s automaton does the same job in $n$ steps: the set of NFA states doesn’t grow with the number of ways the string can be cut. In 2007 Russ Cox showed the difference on a 29-character string and a pattern picked to torment backtracking: Perl took over a minute, Thompson’s automaton twenty microseconds.

Popular engines are built this way because backtracking can do things an automaton can’t: backreferences, “lazy” repetition, lookahead. And on ordinary expressions it is fast. The danger lies in a few shapes: a repetition inside a repetition over the same characters ((x+)+, (a|aa)*), several .* in a row, and alternatives that can match the same text. The lab below lets you try each of these shapes.

The backtracking blow-up, timed on the course server. Pick an expression and press “Measure”: the strings grow until a single check takes more than a second. The time axis can be switched to a logarithmic scale, where an exponential turns into a straight line. With “your own” you can time any expression on strings of the form “prefix + unit × n + suffix.”

Post-mortem: July 2, 2019

We now have everything we need to take apart the outage promised at the start of the chapter. Cloudflare’s CTO, John Graham-Cumming, described it in a public report, and we will follow that report. Cloudflare stands between millions of websites and their visitors: it is a content delivery network from Chapter 34, plus protection against attacks. Requests to the sites it serves are handled by the same processors that run its web application firewall, a set of rules that look for signs of attacks in requests; many of those rules are regular expressions.

Time, UTC	What happened
13:42	An engineer rolls out a new rule against cross-site scripting (XSS). The rule is in “simulate” mode: it blocks no requests, it only flags them. But it still has to run, and under the usual procedure the change goes out to every server in the world at once.
13:45	The first alert. Processors on servers all over the world are at almost 100% load. Visitors to the sites see a 502 error; Cloudflare loses about 80% of its traffic.
14:07	The firewall is switched off worldwide.
14:09	Traffic and processor load are back to normal. The outage has lasted 27 minutes.
14:52	The firewall is switched back on, now without the new rule.

The culprit turned out to be one small piece of the rule: .*(?:.*=.*). (?:…) is a group that remembers nothing; otherwise the expression is three .* in a row, with an equals sign between the second and the third. The expression looks for “anything, then anything, an equals sign, anything.” If the string has no equals sign, the engine tries every place to start the match, every place to end the first .* and every place to end the second: three nested choices, on the order of $n^3$ steps. No exponential here, “only” a polynomial, but the third power was enough. We can reproduce it in the sandbox and compare it with two fixes and with Thompson’s automaton from the cs.automata module.

Each time the length doubles, Cloudflare’s rule gets almost eight times more expensive, as a third power should: on a string of two thousand characters it takes more than half a second, and on a request of a few kilobytes, tens of seconds. And every server was getting thousands of requests a second. The expression .*=.*, which means the same, grows only quadratically and spends about a millisecond on the same strings. The check '=' in s, which is all this part of the rule needed, takes microseconds. Thompson’s automaton, written in pure Python and therefore slow on every character, grows linearly: a hundred thousand characters take it a fraction of a second.

The report goes beyond the regex: one bad formula turned into an outage because several causes came together. The regex engine, PCRE, worked by backtracking and had, in the report’s words, “no mechanism to protect against a runaway expression.” A protection against regexes that ran too long had existed, but it had been removed by mistake a few weeks earlier, when the firewall was being reworked. The rollout procedure let rules go out to the whole world at once, with no trial on a fraction of the servers. And even “simulate” mode executed the rule. Take away any one of these causes, and the unlucky formula would not have become an outage.

Among the fixes Cloudflare announced in the report was a move to RE2 or to Rust’s regex engine: both guarantee time linear in the length of the text, because there are automata inside. Half a century after Thompson’s paper his method was needed again: with an automaton, an outage like this one can’t happen. Python itself has had its own tools since version 3.11: the atomic group (?>…) and the possessive quantifiers *+, ++ forbid the engine to backtrack into a part of the expression that has already matched. And the everyday rules are these: don’t nest repetitions that can eat the same characters; don’t put several .* in a row; limit the length of what you check; and test an expression on long invalid strings as well as on valid ones, as in the email task below.

What an automaton can’t do

On the second day of the expedition in Chapter 50, the islanders started speaking in parentheses: nu opens, ti closes, and the pairs must match. A proof was promised there that a finite automaton can’t check such phrases. Keep only the parentheses of that language: strings of “(” and “)” in which every parenthesis is closed and none is closed too early.

No finite automaton accepts exactly the balanced strings of parentheses.

Suppose such a DFA exists and has $p$ states. Feed it $p$ opening parentheses in a row. Before the first one and after each of them the automaton is in some state: $p + 1$ moments in all, and only $p$ states. By the pigeonhole principle, two of those moments share a state: after $i$ and after $j$ opening parentheses, where $i < j$. Now append $i$ closing parentheses in both cases. The automaton starts from the same state and reads the same symbols, so it ends in the same state as well. But it must accept the string of $i$ opening and $i$ closing parentheses and reject the string of $j$ opening and $i$ closing ones, which leaves some parentheses open. One state can’t be accepting and not accepting at once. A contradiction.

The heart of the proof is that an automaton with $p$ states can’t count past $p$: it mixes up two different histories, “$i$ open” and “$j$ open.” The same argument works for many languages, and it was turned into a general lemma. Rabin and Scott were the first to prove it, in 1959, and soon afterward Yehoshua Bar-Hillel, Micha Perles and Eli Shamir discovered it again.

For every regular language $L$ there is a number $p$ with the following property: every string $w$ in $L$ of length at least $p$ can be cut into three parts, $w = xyz$, so that $y$ is not empty, $|xy| \le p$, and all the strings $xz$, $xyz$, $xyyz$, $xyyyz$, … are in $L$ too.

Let $p$ be the number of states of a DFA for $L$. While reading the first $p$ characters of $w$, the automaton is in a state $p + 1$ times, counting the start, so some state repeats: after $x$ and after $xy$ it is in one and the same state. So the piece $y$ takes the automaton around a loop, from a state back into itself. The loop can be traveled zero times, once, twice, any number of times: afterward the automaton is in the same place, reads $z$ along the same path and ends in the same accepting state.

The lemma is called the pumping lemma: the piece $y$ can be “pumped” by repeating it. It is used to prove that a language is not regular: find a long string in the language that can’t be pumped in any way without leaving the language, and the language is not regular. It helps to think of this as a game. Your opponent claims that the language is regular and names $p$. You choose a string in the language at least $p$ long. The opponent cuts it into $x$, $y$, $z$ by the rules of the lemma. You choose how many times to repeat $y$. If the result is not in the language, you win. If you have a way to win whatever your opponent does, the language is not regular.

The pumping game. Choose a language, enter a string and press “Hand it over”: your opponent will cut it into $x$, $y$, $z$, trying to make sure that pumping can’t take it out of the language. Then choose how many times to repeat $y$, and see whether the string stays in the language. For a regular language, the opponent always finds a cut you can’t break. Try it and see.

Parentheses need a counter that can grow without limit, and if there are several kinds of brackets, a stack, as in Chapter 15, where we used one to check them. A finite automaton given a stack is called a pushdown automaton, after the spring-loaded stack of plates in a cafeteria: the plate pushed down last comes off first. Its languages are the context-free languages of Chapter 50, and the recursive descent parser you wrote there is such an automaton too, with Python’s call stack as its stack.

The ladder of machines

Chomsky’s table from Chapter 50 can now be read as a ladder of machines, where each rung adds memory. At the bottom is the finite automaton: no memory, only a state. It accepts the regular languages: numbers, dates, phone numbers, the tokens of a programming language. One rung up is the automaton with a stack: it counts and checks nesting, and its languages are the context-free ones, which include the syntax of almost every programming language. Higher still is a machine with a tape as long as the input string, which it can travel in both directions and write on; its languages are called context-sensitive, and among them are strings like “a…a b…b c…c” with equally many of each letter. And at the top is the same machine with an infinite tape. This four-rung ladder is called the Chomsky hierarchy.

Python’s regexes don’t fit on this ladder. With backreferences they check “a word repeated twice,” which is beyond even a pushdown automaton. Yet balanced parentheses nested to any depth are beyond the re module. So the word “regular” in its name is a tribute to history: under the hood there is backtracking, with powers and dangers of its own.

The more memory a machine has, the more languages it recognizes, and the harder it is to prove anything about it. About a finite automaton you can learn everything: whether it accepts anything at all, whether two automata are equivalent; there are fast algorithms for all of it. About a machine with an infinite tape, as we will soon see, you can’t even learn whether it will stop.

Tasks

Five tasks. Three are regexes you will need tomorrow: a date, a phone number, an email address, and each hides a common trap. Two are about automata: run a DFA, and build one from an NFA.

Write parse_date(text): if the string is a date written as “month/day/year,” return a tuple of three integers (month, day, year); otherwise return None. The month runs from 1 to 12 and the day from 1 to 31, each with one or two digits (9/1/2026 and 09/01/2026 both work); the year has four digits, from 1000 to 2999. Whether February has a 30th is not your concern: that is a job for the datetime module. The string must be a date and nothing more, with no spaces or other characters around it, and the digits must be ordinary ones, 0 to 9.

A regex describes a range of numbers by listing the cases. The day is an optional zero and a digit from 1 to 9, or 1–2 and any digit, or 3 and 0–1: 0?[1-9]|[12][0-9]|3[01]. The month is built the same way, only shorter. Don’t forget to put the “or” in parentheses: without them, | cuts the whole expression in two.

Even with the numbers fixed, the starter trips twice. re.match with $ accepts '1/1/2000\n': in Python, $ also matches before a final newline. Check the whole string with re.fullmatch. And \d in Python means any Unicode digit, including Arabic-Indic ones like ٢٠٢٤; write [0-9].

The expression is compiled once, with re.compile, and used many times: that is faster and easier to read. Both traps from the second hint are common in practice: because $ matches before a final newline, strings with a trailing newline slip into logs and forms, and \d lets in digits that different parts of a program will later read differently. Whether April has a 31st is better left out of the regex: datetime.date(year, month, day) raises an exception on its own.

People write phone numbers any old way: +1 (912) 345-6789, 912-345-6789, 9123456789. Write normalize_phone(text), which brings a valid number to the form +19123456789 and rejects an invalid one by returning None. A valid number is a country code, +1 or 1, which may be left out; then a three-digit area code, possibly in parentheses, like (912); then the seven digits of the number, together, like 3456789, or as three and four, like 345-6789. Between the groups there may be one space, one hyphen or nothing. No other characters are allowed in the string.

The starter throws away everything but digits and so accepts junk: +1 (912 345-6789 with an unclosed parenthesis, tel. 9123456789, 912 345 6789 with a space in front. Describe the shape of the number in full and check it with re.fullmatch.

An area code with or without parentheses is an “or” of two variants: (?:$([0-9]{3})$|([0-9]{3})). Only one of the two groups will match, and the other will be None, so you fetch the code as m.group(1) or m.group(2). An optional separator is [ -]?.

The regex copes with the parentheses around the area code, even though “parentheses are beyond an automaton”: here there is only one pair, the depth of nesting is bounded, and the automaton only has to remember whether the pair is open. Only unlimited depth is impossible. The optional country code takes its separator along with it into one group: otherwise a number without a code could start with a stray space or hyphen. And seven digits in a row and 345-6789 both pass because the separators are optional: the groups of 3 and 4 digits may stand side by side.

The email check in the starter gives the right answer on every ordinary string. But on one long string without an @ it runs longer than any server stays up. Fix PATTERN so that is_email gives the same answers and handles any string tens of thousands of characters long in a fraction of a second. The rules for an address: the name is words made of the letters A–Z (in either case) and digits, separated by a single dot, hyphen or underscore (a separator can’t come first, last or twice in a row); then @; then the domain, parts made of the letters A–Z, digits and hyphens (a hyphen can’t start or end a part), separated by dots, at least two parts, the last of them letters only and at least two letters long.

Run the tests: correctness passes, but on a string of forty letters a and an exclamation mark the check doesn’t finish in the time allowed. The first group is to blame: ([A-Za-z0-9]+[._-]?)* is a repetition inside a repetition, and the separator in it is optional. This group can cut the string aaaa into pieces in $2^{n-1}$ ways, like (x+x+)+ in the section on backtracking.

Make sure that each piece of the string can be assigned to the expression in only one way. Let every repetition begin with a required separator: a word, then any number of “a separator and a word.” The domain in the starter is already written like that.

The language hasn’t changed; the ambiguity has gone. In {WORD}(?:[._-]{WORD})* every round of the repetition has to begin with a separator, so it is clear from the string itself where one word ends and the next begins: there is no reason to go back and try another cut. Such an expression runs in close to linear time, even though the engine still backtracks. The same remedy, removing ambiguity, would have saved Cloudflare’s rule too. Email addresses in the wild are more complicated (a name can contain +, quotation marks and even spaces), so in practice an address is checked with a simple expression and then sent an email with a link.

An automaton is given as a dictionary: "start" is the start state, "accept" the set of accepting states, "delta" the transitions {(state, symbol): state}. The turnstile, for example: {"start": "locked", "accept": {"unlocked"}, "delta": {("locked", "c"): "unlocked", …}}. Write two functions. run_dfa(dfa, text) returns True if the automaton accepts the string; if some symbol has no transition, the string is rejected. divisible_dfa(k) builds, in the same format, an automaton over the symbols "0" and "1" that accepts the binary representations of the numbers divisible by k (leading zeros are allowed, and the empty string stands for 0) and has at most k states. One of the tests is a number with 317 thousand binary digits.

dfa["delta"][(state, ch)] raises KeyError when there is no transition, and the answer you need is “rejected.” The dictionary method .get returns None instead, and then you can return False right away.

For divisibility, recall the “by three” automaton from “A machine without memory”: the state is the remainder of the number read so far, and a digit b appended on the right takes the remainder r to (2 * r + b) % k. The states are the numbers from 0 to k - 1; the start and the only accepting state is 0.

The transition table is a dictionary, and one step of the automaton costs one lookup, so 317 thousand digits are read in a fraction of a second: the time is linear, and the memory doesn’t grow at all. A missing transition is the usual way to say “no road from here”: textbooks draw an extra “dead” state that can never be left, and programs don’t store it at all. There are k remainders, and fewer states are possible only for special values of k: for even ones from 4 up, for example, some states can be merged. Finding the smallest automaton for a given language is the job of the minimization algorithm, one more thing you can learn about a finite automaton quickly.

Write to_dfa(nfa), the subset construction. An NFA is given as a dictionary: "start"; "accept", the set of accepting states; "delta", the transitions {(state, symbol): set of states}; and possibly "eps", the ε-transitions {state: set of states}. Return a DFA in the format of the task “Run an automaton,” where each state is a frozenset of NFA states. The start state of the DFA is every state the NFA can reach from its start by ε-transitions (the start itself included). The DFA must contain only states reachable from its start, and no transitions into the empty set. The alphabet is the symbols that occur in "delta". The tests compare your DFA with the NFA on hundreds of strings and build a DFA with 4096 states.

The starter is right for an NFA without ε-transitions, and it passes the first test. One thing is missing: after every step, and before the first one too, the set has to gain every state reachable from it by ε. This is the ε-closure.

The ε-closure is a search over the graph of ε-transitions from all the states of the set at once, like the depth-first search of Chapter 19: a stack, a set of visited states, and while the stack isn’t empty, pop a state and push its unvisited neighbors. Return a frozenset, so that the set can go into another set and serve as a dictionary key.

A queue on list.pop(0) still copes with 4096 states, but every such pop shifts the whole list; collections.deque from Chapter 15 takes from the front in $O(1)$.

Two searches are nested: the outer one, breadth-first, walks over the states of the DFA, and the inner one, depth-first, computes the ε-closure. Every set that holds at least one accepting state of the NFA becomes accepting: “at least one guess succeeded.” For the automaton in the tests, Thompson’s NFA for (a|b)*abb with eleven states, you get five states, and the start is {0, 1, 2, 4, 7}: that many places where the NFA can stand before it has read a single letter. Run to_dfa and then run_dfa from the previous task, and you have a working regex engine without backtracking, like the egrep of 1979.

What next

The finite automaton turned out to be a machine you can learn everything about, and one that can do little. It can’t count parentheses or compare the two halves of a string: its whole past is squeezed into one of finitely many states. A stack helped with parentheses, but a stack has its limit too. With a stack you can’t check strings like “a…a b…b c…c” with equally many of each letter: to compare the a’s with the b’s you have to pop them off the stack, and then nothing is left to compare with the c’s.

What if we gave the automaton memory with no limits at all? Let it have an infinite tape of cells and a head that reads a cell, writes a symbol into it and moves one step right or left. The transition table is almost the same as the turnstile’s: given the state and the symbol read, it says what to write, where to move and which state to go to. In 1936 the 23-year-old Alan Turing came up with this machine and claimed that it could do everything that can be computed by rules at all: everything that Python, Iskra-8 or a person with a pencil and an endless notebook can do. It is the subject of the next chapter. And in the chapter after it we will return to the question this one started with: can we tell whether such a machine will ever stop?