Following Every Path at Once, So Nothing Ever Has to Be Undone
Last timeThe Machine It Turns Into
An engine that carries the set of states a machine could be in reads each character once, never backtracks, and costs the input length times the machine size.
A pattern with a choice in it becomes a machine with a choice in it, and a
machine standing at a choice has no information with which to make it. The
character that would settle the question has not been read yet.
One way out is to guess, carry on, and come back to the choice if the guess
turns out badly. The other way out is to stop guessing. Follow every branch of
the choice at the same time, and hold not a state but the set of states the
machine could now be in. Nothing is ever wrong, so nothing is ever undone, and
the cost of a whole run can be written down before a single character of input
has been seen.
The machine, and the one place it has a choice
The pattern under examination throughout is : the letter a, then
any number of b or c characters, then the letter d. It matches ad, abd, acd,
abbcd and abccd, and it does not match abc, da or abcd followed by anything
else.
That pattern becomes a machine with four states. State 1 is the start and state
4 is the only accepting one. State 1 reads an a and moves to state 2. State 2
is the top of the repetition, and from there the machine has two things it may
do: take an edge that reads nothing at all into state 3, which is the body of
the repetition, or read a d and finish in state 4. State 3 reads either a b or
a c and returns to state 2.
The edge that reads nothing is the whole difficulty. A machine whose every edge
carries a label is a machine with no decisions in it: read the character, look
at the one edge that matches, move. An edge that reads nothing can be taken at
any moment, including a moment at which taking it is a mistake, and the machine
has no way to tell.
The lesson stops here
6 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 planThe contentsThis 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