The Set of Strings a Pattern Accepts, and the Three Operations That Build It

A pattern names a set of strings rather than a way of searching, and every convenience in the notation rewrites into one atom and three operations once it is written out.

A pattern is usually explained as a set of instructions for searching. Find an

a, then take b or c for as long as you can, then find a d. That explanation

survives about a week of use, and then it starts to mislead, because it

describes a method rather than a meaning, and the methods differ between tools

while the meaning does not.

The meaning is the simpler of the two. A pattern is a description of a set of

strings, and nothing else. Asking whether a pattern matches a string is asking

whether that string belongs to the set, and the set is settled by the pattern

alone, before any program has been chosen to decide the question.

What a pattern is a description of

Write $L(e)$ for the set of strings the pattern $e$ accepts. The letter stands

for language, which is the usual word for a set of strings, and that is all it

means here.

The entire definition fits in four lines. Each line says what $L$ is for one

way of writing a pattern, in terms of $L$ of its parts, which is what makes it

a definition rather than a collection of examples. A pattern of any size is

taken apart into smaller patterns until single characters are left, and the set

is assembled on the way back up.

FIG 1The set a pattern describes, defined on the pattern's own structure

: the set of strings the pattern e accepts, which is the whole of what the pattern means
: a single literal character, the one thing in the notation that is not built from something smaller
: the string u with the string v written immediately after it, with nothing between them
: the strings made by joining k members of L(e) end to end, with the case k equal to zero giving the set whose only member is the empty string

Four lines and three of them are operations, since the first is the atom. Read the third one carefully: it does not say the two parts match in order, it says the string splits somewhere into a piece the first part accepts and a piece the second accepts, and nothing fixes where the split is. That is why a sequence of two patterns can be satisfied in several ways by one string, and it is the root of every disagreement about which match an engine returns. The fourth line is the one that has to be read twice, and the rest of this page comes back to it.

Take the running example used throughout, a pattern matching an a, then any

number of b or c characters, then a d. Written with brackets for grouping it is

$a(b \mid c)^{\ast}d$ . Taken apart, it is a sequence of three things: the

literal a, the repetition $(b \mid c)^{\ast}$ , and the literal d. The body of

the repetition is a choice between two literals.

So the set builds like this. $L(b) = \{b\}$ and $L(c) = \{c\}$ , so

$L(b \mid c) = \{b, c\}$ by the union line. The repeated set is every string of

b and c characters in any order and any quantity, the empty one included.

Joining an a in front of each of those and a d behind each gives the set for the

whole pattern, which holds ad, abd, acd, abbd, abcd, acbd, accd, and so on

without end.

Notice what has not been mentioned once. No scanning, no position in the input,

no leftmost anything, no going back and trying again. All of those belong to a

method for deciding membership, and there is more than one such method. The set

does not know which one is being used on it.

That gap is the most useful idea on this page, because it explains two things

that otherwise look like folklore. The first is that a pattern can be rewritten

freely so long as the set is unchanged, which is what every rewriting inside an

engine depends on. The second is that two engines can disagree about which part

of a string matched while agreeing exactly about whether it matched, because the

set says which strings belong to it and says nothing whatsoever about which

match to hand back.

One atom and three operations

A single literal character is the atom. The three operations are choice,

sequence and repetition.

Choice, written with a vertical bar, accepts anything either of its two parts

accepts. In set terms it is union, so the result has at most the sum of the two

sizes.

Sequence, written by putting two patterns next to each other with nothing

between them, accepts a string that splits into a part the first accepts

followed by a part the second accepts. In set terms it is the set of all pairs

joined end to end, so the result has at most the product of the two sizes. Two

characters of notation that multiply set sizes are the reason the notation is

worth having.

Repetition, written with a star after a pattern, accepts any number of copies of

that pattern joined end to end. Any number includes none, and the next section

is entirely about that.

The brackets are worth a sentence, because they are not a fourth operation.

They say which part of the written pattern groups with which, exactly as in

arithmetic, which means a pattern has fewer parts than it has characters.

$a(b \mid c)^{\ast}d$ is eight characters and six parts, those being four

literals, one choice and one repetition. Counting the parts rather than the

characters is what matters later, because the size of the machine a pattern

becomes is counted in parts.

The claim that goes with a list of three is a completeness claim, and it is a

strong one. Everything else in the notation, every class, every counter, every

optional marker, every convenience that makes a real pattern readable, rewrites

into literals and these three.

The repetition that runs no times

The fourth line of the definition says that the repeated set is the union over

every count $k$ from zero upwards of $L(e)^k$ . The term everybody skips is the

one for $k = 0$ .

$L(e)^0$ is the set containing exactly one string, the empty string, written

$\varepsilon$ . It is not the empty set. Those two objects look alike written

down and are nothing alike: the empty set has no members and corresponds to a

pattern that accepts nothing at all, while the set containing the empty string

has one member and corresponds to a pattern that succeeds while consuming no

characters.

So the empty string belongs to the repeated set for every pattern, without

exception, and three things follow that read like defects until the definition

has been seen.

The shortest string $a(b \mid c)^{\ast}d$ accepts is ad, two characters, with

the repetition running zero times. A pattern all of whose parts are repeated

accepts the empty string, so it succeeds at every position of every input,

including the position after the last character. And a test for whether some

text contains a digit, written as a repeated digit class, answers yes for every

string it is ever given, matching nothing at position zero. None of this is a

quirk of a particular tool. It is what the definition says.

FIG 2Three shorthands written out in literals and the three operations

step	as written	in literals and the three operations	literals in the expansion	operations in the expansion	what happened
1	[0-9]	0\|1\|2\|3\|4\|5\|6\|7\|8\|9	10	9 choices	a class is a choice and the brackets are a way of writing a ten way choice in five characters
2			twice whatever e holds	1 repetition and 1 sequence more than e	one copy, then any number including none, which together is one or more
3			four times whatever e holds	3 sequences and no repetition at all	a counter is not a loop once expanded, it is that many copies written out

3 steps

The third row is the one with a sting in it. A counted repetition contains no repetition operation whatsoever after expansion, which is why it is the one shorthand whose cost is proportional to the number written inside the braces: a counter of a thousand is a pattern a thousand times longer than the four characters it occupies. Two further shorthands follow the same move and are left out of the table only because they are one line each. A question mark is a choice against the empty pattern, so e followed by a question mark is e or nothing. A dot is a choice across every character the alphabet allows, which is usually every character except the line ending.

Every shorthand is one of the three in disguise

A character class in brackets is a choice. The class of digits is

$0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9$ and nothing

more, and a range inside the brackets is just a way of naming consecutive

characters, so the class of lower case letters abbreviates a twenty six way

choice.

A plus is a sequence followed by a repetition. One copy, then any number of

further copies including none, is exactly one or more.

A counted repetition is a sequence of copies, so four copies of $e$ is

$e\,e\,e\,e$ with no star anywhere in it.

The reason to do this expansion once by hand is that the expansion is what

everything afterwards is measured against, rather than the characters that were

typed. Take the practical pattern used throughout, a date written as four

digits, a dash, two digits, a dash and two digits, which as written is

$[0-9]\{4\}-[0-9]\{2\}-[0-9]\{2\}$ and occupies twenty two characters. Expanded,

there are eight digit positions in it, four from the year and two from each of

the other groups. Each position is ten literals joined by nine choices. So the

expansion holds $8 \times 10 = 80$ digit literals plus the two dash literals,

which is 82 literals, and $8 \times 9 = 72$ choices. A pattern of twenty two

characters is a pattern of 154 parts, and every later count of what it costs is

taken on the 154.

How many strings is that

The set the running example describes is infinite, so counting it whole tells

you nothing. Counting it one length at a time tells you a great deal.

A string of total length $n$ accepted by $a(b \mid c)^{\ast}d$ has an a at the

front, a d at the back, and $n - 2$ characters in the middle, each of them

independently b or c. There are therefore $2^{n-2}$ accepted strings of length

$n$ , for every $n$ of at least two.

FIG 3How many strings the running pattern accepts at each length

	2	3	4	5	6	7	8
characters in the repeated middle	0	1	2	3	4	5	6
strings of exactly that total length	1	2	4	8	16	32	64

The columns are total lengths and the bottom row is two raised to the middle length above it. The left marked cell is the single shortest accepted string, ad, where the repetition ran no times, and it is the cell most readers would have left out. The right marked cell says there are sixty four accepted strings of length eight. Carrying on, length ten gives two to the eighth, which is 256, and the total number of accepted strings of length ten or less is one plus two plus four and so on up to 256, which is two to the ninth less one, that is 511. Each extra character of input doubles the count, so eight characters of pattern are a finite description of a set growing as fast as anything can grow, and that is the whole trade the notation makes.

The set you described and the set you meant

Now the practical version of the same count. The date pattern accepts a four

digit group, a dash, a two digit group, a dash and a two digit group. How many

strings is that?

Each digit position is one of ten choices, the positions are independent, and

there are eight of them, so the count is $10^8$ , which is 100,000,000. The two

dashes are fixed and contribute a factor of one each.

How many of those hundred million strings are a date? Read the four digit group

as a year from 0000 to 9999. A Gregorian span of ten thousand years holds

$10000 \times 365 = 3{,}650{,}000$ ordinary days, plus one extra day for each

leap year in the span. The leap years are those divisible by four, less those

divisible by one hundred, plus those divisible by four hundred, which is

$2500 - 100 + 25 = 2425$ . So there are $3{,}650{,}000 + 2425 = 3{,}652{,}425$

real dates in the range the pattern covers.

FIG 4What the date pattern accepts, divided by what it is

The arithmetic for each slice. Strings whose middle group is not one of the twelve month numbers come to ten thousand years times eighty eight bad month values times a hundred day values, which is 88,000,000. Strings with a real month come to ten thousand times twelve times a hundred, which is 12,000,000, and taking the 3,652,425 real dates out of that leaves 8,347,575 with a plausible month and an impossible day. The three slices add to exactly 100,000,000, and the real dates are 3.65 per cent of the total, one string in every 27.4. No rewriting of a pattern of this shape closes that gap, because it cannot count the days in a month and cannot know which years are leap years.

So 96,347,575 of the strings this pattern accepts are not dates. The string

2026-13-45 is one of them, and so is 0000-00-00. The gap between the two counts

is where this entire category of bug lives, and the honest division of labour is

to let the pattern say what the shape is and let something that can do

arithmetic say whether the value is possible.

Reading a pattern from the inside out

The definition is short enough to be a program, and writing it out is the

fastest way to be sure that four lines really are all there is.

FIG 5The whole definition, as twenty lines that decide membership

python

def accepts(e, s):
    return any(left == '' for left in prefixes(e, s))

def prefixes(e, s):
    kind = e[0]
    if kind == 'lit':
        return [s[1:]] if s[:1] == e[1] else []
    if kind == 'or':
        return prefixes(e[1], s) + prefixes(e[2], s)
    if kind == 'seq':
        return [t for r in prefixes(e[1], s) for t in prefixes(e[2], r)]
    if kind == 'star':
        out = [s]                              # the k = 0 term, always present
        for r in prefixes(e[1], s):
            if r != s:                         # a copy that consumed nothing would loop
                out += prefixes(e, r)
        return out
    raise ValueError(kind)

bc = ('or', ('lit', 'b'), ('lit', 'c'))
small = ('seq', ('lit', 'a'), ('seq', ('star', bc), ('lit', 'd')))

One case per line of the definition and no cases left over. The function returns every way the pattern can match a prefix of the string, reported as what is left over afterwards, and accepting the whole string means an empty leftover appears somewhere in that list. On the running pattern it says True for ad, where the repetition ran no times, True for abccbd, False for abc, which has no d, and False for aad, whose second character is in neither branch of the choice. Two lines are worth staring at. The line that starts the star case with the string untouched is the k equal to zero term, and deleting it breaks ad while leaving everything else working, which is why that bug survives a test suite. The guard that refuses a copy consuming nothing exists because a body that can match the empty string would otherwise be tried for ever: that is a property of this method and not of the set, which was perfectly well defined before any program existed.

Twenty lines, no tables, no machines, nothing that looks like an engine. It is

also exponentially slow on the wrong input, because a sequence of two patterns

has to try every place the string could split and the trials multiply when

sequences nest. That is a fact about this method rather than about the set, and

it is the reason the thing worth building next is not a cleverer recursion but a

machine with a fixed number of states, whose cost can be counted before it is

run.

Recap

A pattern is a description of a set of strings, so asking whether it matches is asking whether a string belongs to that set, and the set is settled by the pattern alone before any engine has been chosen to decide the question.
Every pattern is built from literal characters and exactly three operations, which are a choice between two patterns, one pattern followed by another, and a pattern repeated any number of times.
A repetition always includes the case of no copies at all, which is why a pattern whose every part is repeated accepts the empty string and therefore succeeds at every position of every input.

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

NextThe Machine It Turns Into →