Building by Hand the Machine a Pattern Turns Into
Last timeA Pattern Describes a Set of Strings
One rule for each of the three operations turns a pattern into a machine of states and edges, and the machine comes out no larger than about twice the pattern.
A pattern describes a set of strings and says nothing about how to decide
membership of it. Something has to decide, and the thing that does is a
machine: a fixed number of states, edges between them carrying characters, one
state to start in and at least one state that means yes.
The useful fact about this translation is that it is mechanical and it is
small. There is one rule for each of the three operations, the rules can be
applied by hand in a few minutes, and the machine that comes out is no bigger
than about twice the pattern that went in. Everything later that promises a
cost is promising it in terms of that size, so the size is worth counting
exactly once, carefully, on an example small enough to draw.
What the machine is made of
A machine here is four things. A set of states, drawn as boxes and numbered. A
set of edges, drawn as arrows, each one labelled either with a character it
reads or with nothing at all. One state nominated as the start. And one or more
states nominated as accepting.
To run the machine on a string, begin at the start state and follow edges. An
edge labelled with a character may be followed only when the next character of
the input is that character, and following it consumes that character. An edge
labelled with nothing may be followed at any time and consumes nothing. The
string is accepted when some way of following edges consumes the whole of it
and finishes in an accepting state.
Two words in that paragraph are doing a great deal of work. Some way, not
every way, which is why a machine may wander down a path that fails without
that meaning the string is refused. And finishes, which is why stopping in a
non accepting state with input still in hand is not the same as failing
part way through.
One rule for each operation
Every piece of a pattern is built as a machine fragment with exactly one entry
state and exactly one exit state. That invariant is the whole trick, because it
means a rule can be applied to a piece while knowing nothing about what is
inside it.
A literal character needs two states, an entry to leave from and an exit to
arrive in, with one edge between them labelled with that character.
A sequence of two pieces needs no new state. Identify the exit of the first with
the entry of the second, and the result has the first piece's entry and the
second piece's exit. One state has been merged away.
A choice between two pieces needs no new state either. Identify the two entries
with each other and the two exits with each other, since both branches start
from the same place and both finish at the same place. Two states have been
merged away.
A repetition needs one new state, which is both the entry and the exit of the
result. Add an edge from it that reads nothing into the body's entry, and
identify the body's exit with the new state so that finishing the body puts the
machine back where it decides again. One state has been merged away and one new
one added.
The lesson stops here
5 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