Back References, Look Around and Why Brackets Cannot Be Matched

Last timeWhen Matching Blows Up

Which familiar features a finite machine can carry out and which cannot be one at all, with the argument for why no pattern matches balanced brackets and what a bounded depth costs instead.

Some of the things written with patterns every day are not patterns. A back

reference that insists the closing tag matches the opening one, a look ahead

that requires a digit somewhere in a password, a construct that lets a pattern

call itself so that brackets can be counted: these sit in the same notation,

behind the same function call, and they are not the same kind of object. One of

them is still a pattern in the original sense and is merely slow. Two of them

have left that world entirely, and the usual advice about nesting and brackets

follows from which is which.

Separating them needs one number, and it is the number of states.

The whole memory of a finite machine

Write $q$ for the number of states in the machine a pattern compiles to, and

$n$ for the largest run of characters the pattern is supposed to keep track of.

Standing in a state is everything the machine knows. It has no variables, no

counter and no copy of the characters it has read, so when it reads the next

character the only thing carrying information forward is which of the $q$ boxes

it is in.

FIG 1The memory a machine of q states has, and the states counting to n needs

: how many states the machine has, which grows with the length of the pattern
: bits of information the machine carries from one character to the next
: the largest run the pattern has to keep track of, which grows with the input

A pattern that matches an a, then any number of b or c, then a d compiles to four states, so its whole memory is the two bits of log base two of four, and two bits distinguish four situations and never a fifth. The second relation is the one that bites. To tell apart no a characters, one a, two a and so on up to n of them, the machine needs a distinct state for each, which is n plus one states; counting to a hundred therefore needs at least 101 states, and counting to any number at all needs more states than any fixed machine has.

Both halves of that figure matter. The first says the memory is two bits, which

sounds damning and is not quite the complaint, because a longer pattern compiles

to a bigger machine and two bits becomes ten. The second says what the real

complaint is. The states come from the pattern and are fixed when it is

written; the thing to be counted comes from the input and is not. Whatever $q$

a pattern buys, an input needing $q+1$ situations is one character longer than

the input that needed $q$ .

The lesson stops here

10 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

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

Back References, Look Around and Why Brackets Cannot Be Matched

The whole memory of a finite machine

10 more paragraphs to go

This is the reading half

Read alongside