Collapsing a Set of States Into One Lookup Table, and What That Table Can Cost
Last timeFollowing Every Path at Once
Turning every reachable set of states into a single state gives one table lookup per character, and there are short patterns whose table has two to the power of k rows.
An engine that carries a set of states does some of its work twice. Running the
four state machine for over the input abccd, the set of states 2
and 3 is produced three times, and each time the same question is asked of it:
given this set and the character c, which set comes next? The answer cannot
change. It depends on the set and the character and on nothing else, least of
all on where in the input the set was reached.
So work it out once and write it down. Give every set that can arise a name, and
record for each name and each character the name of the set that follows. The
result is a table, and a machine driven by that table has no choices left in it
at all.
One state per set of states
Name the quantities first. Let be the number of states in the machine with
choices, the number of characters in the input, and a parameter of a
pattern family introduced later on this page.
The construction is the set carrying engine with its answers remembered. Begin
a work list holding one set, the closure of the start state under the edges that
read nothing. Take a set off the list. For each character of the alphabet, work
out the set that follows it in the usual way, by following the labelled edges
out of every state in the set and closing the result. If that set has been seen
before, write its existing name into the row. If it has not, give it a new name
and put it on the work list. Stop when the list is empty.
The order matters in one place. A set must be closed before it is compared with
the sets already seen, because the same set reached by two routes has to get one
name, and an unclosed set together with its closure would be filed as two.
| step | set taken off the work list | on a | on b or c | on d | new sets put on the list | what happened |
|---|---|---|---|---|---|---|
| 1 | A, the closure of state 1 | B | D | D | B and D | The start set is closed before anything is looked up. Here state 1 has no edge that reads nothing, so A holds state 1 alone, and the a edge leads to state 2 whose closure also contains state 3. |
| 2 | B, holding states 2 and 3 | D | B | B | none | Provisional. Both b and c send state 3 back to state 2 and the closure puts state 3 back, so the repetition has become a self loop on a single row. |
| 3 | B, corrected on the d column | D | B | C | C | State 2 reads the d into state 4, whose closure is state 4 alone, so the d column of B is the new set C rather than B. |
| 4 | C, holding state 4, accepting | D | D | D | none | State 4 has no edges at all, so every character leaves the language and lands in the empty set. |
| 5 | D, the empty set | D | D | D | none | The empty set sends every character back to itself, the work list is now empty, and the construction has finished with four rows out of a possible sixteen. |
| on a | on b | on c | on d | |
|---|---|---|---|---|
| A, holding state 1, the start | 2 | 4 | 4 | 4 |
| B, holding states 2 and 3 | 4 | 2 | 2 | 3 |
| C, holding state 4, accepting | 4 | 4 | 4 | 4 |
| D, the empty set | 4 | 4 | 4 | 4 |
Reading an input is now one lookup per character. Start at A, index the row by
the character, move to the row named in the cell, and at the end of the input
ask whether the row reached is an accepting one. There is no set to hold, no
closure to compute and nothing to add together while the input is being read.
The saving is worth a number. On this machine the set carrying engine follows
up to five edges at a character, one of which reads nothing, and it builds a
fresh set each time; the table follows none and builds nothing. Per character
it performs one array index and one comparison, and that figure does not
mention the pattern at all, where the set engine's per character cost grows
with the machine. This is why a table is what a tool produces when it is
handed a specification once and asked to run it over every file in a build:
the construction is paid for at the moment the specification is read, and the
reading of input afterwards is as cheap as reading input gets.
Four rows is also the fewest this pattern can have, and checking that is worth
doing once by hand. Separate the rows that accept from the rows that do not,
giving the accepting group C and the group A, B and D, then split any group
whose members send some character into different groups. The a, b and c
columns split nothing, because every row in the larger group sends those
characters somewhere in the larger group. The d column splits it, since B
reaches the accepting group while A and D stay where they are, leaving C, then
B, then A and D together. One more pass separates A from D on the a column,
because A reaches B and D does not. Four groups, four rows, nothing to merge.
Knowing that the procedure exists matters because a construction straight from
a pattern often does produce rows that are genuine duplicates. Knowing not to
rely on it is the next section.
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