The first stage de Bruijn diagram shows which rows of cells can form a still life (or other pattern). The second stage selects a width, then determines all possible rows of that length. A new de Bruijn diagram, whose links are these rows, describes strips of fixed width but arbitrary height embodying the desired pattern.
It is natural to ask why a fixed width is required. Amongst other representations, the admissible rows can be defined by regular expressions. From the expressions defining the link sequences (three rows high) can be extracted those defining the node sequences (two rows high); compatible rows would be described by intersections of regular expressions. It would seem that one has an instance of Post's correspondence problem, in trying to relate the two classes of regular expressions. Keeping the width fixed and finite eliminates this uncertainty from the calculation.
The simplest criterion for a row is that it be periodic, which means that it would be formed from loops of the first stage diagram of a given length. Other boundary conditions could be imposed, but they would seem to be rather artificial unless the context determining them were included. One possibility, somewhat contrary to the spirit of the generality being described, would be to build up a collection of still lifes with given boundaries. Matching such strips to get even wider strips would reveal some, but not all, of the still lifes having the the composite width.
A very important exception to the reccommendation to eschew such constructions is when the quiescent state forms the boundary. If the de Bruijn diagram contains a link connecting the quiescent state to itself, isolated patterns can be formed. If in turn the strips themselves are bounded by the quiescent state, there will be free standing figures which can exist in complete isolation from any others.
If ``0'' is the quiescent state, we need to concentrate on the (0,0) element of the connection matrix. In any event, suppose that the following illustration represents two consecutive rows of a strip of width 6,
This time the cells are the rows ghijkl and mnopqr with the respective neighborhoods and partial neighborhoods
It is typical of the second stage that there are many broken loops and
even isolated nodes, in contrast to the first stage where they are
relatively infrequent. The same informal probabilistic arguments given
for the first stage explain why. The full diagram for a strip of width
N would have 
nodes with 
links, thus 
links per
node. But instead of a single neighborhood, half of whose links might
be bad, there are N cells, whose ``halves'' are compounded, reducing
the number of good links for the whole row by a factor of 
; the two effects compensate, leaving us with an estimated single
link per node. Fluctuations can just as readily leave a node without a
link as provide it with a pair of links, so that the surviving core of
loops---the ergodic set---will still have a certain amount of variety.
One dreads to think of what would happen if this reasoning remained valid for a third stage, as in a three dimensional cellular automaton.
Although the simplest cases are almost trivial, they are also easy to understand, which will help to fix our ideas and understand the general case.
Figure 4: second stage de Bruijn diagram for width 1
Choosing width 1 means working with constant rows; such a system is a one dimensional linear cellular automaton evolving according to Wolfram's Rule 22. Our table predicts three still life neighborhoods out of eight possible; the pertinent de Bruijn diagram is shown in Figure 4. There is just one still life, discounting the quiescent state; it consists of alternating rows of live and dead cells.
Although this is the simplest case, it already shows some structure, namely that the de Bruijn diagram can consist of two disconnected pieces. It also shows how links and nodes can be dropped from the full de Bruijn diagram. Showing the actual diagram as a subset of the full diagram would be more instructive if a larger diagram were used, but showing complete diagrams for greater widths is too cumbersome for the printed page.
Figure 5: second stage de Bruijn diagram for width 2
Width 2 shows slightly more variety. It is equivalent to working with a (4,1) cellular automaton (4 states, first neighbors).
The unrefined de Bruijn diagram has 11 nodes with 23 links, which reduces to 7 nodes with 19 links and finally to the cyclic core with 7 nodes and 9 links shown in Figure 5. Inspection shows that the de Bruijn diagram decomposes into three disjoint pieces. The first contains just the quiescent state linked to itself; of course we can ascribe any periodicity to the quiescent state that we wish, making it a common feature of all diagrams.
The second is really double the configuration of width 1, in which rows of live cells alternate with rows of dead cells. There is just one new configuration, the third piece, a sort of grillework in which the minimum length of each tier of vertical bars is two cells. Both these latter configurations have to extend indefinitely, since there is no transition bringing either of them to the quiescent state.
Figure 6: second stage de Bruijn matrix for width 3 - connected component
of 00
In contrast to narrower strips, width 3 is striking both for the complexity of its still lifes and the simplicity of the rule generating some of them. The de Bruijn diagram is too complicated to show; however its two disconnected pieces can be exhibited in matrix form.
The first, consisting of 30 nodes, is the least regular, but is the connected component of the quiescent state. If pairs of octal numbers are used to index the nodes, each each member of the pair translates directly into a three-cell cross section of the strip. The pertinent connectivity matrix is shown in Figure 6.
In all diagrams and connectivity matrices a certain amount of symmetry must be present, because the rule of evolution remains the same even though the row from which the diagram is derived is longitudinally shifted or even reflected. The symmetry can manifest in various forms according to whether the still life has the same symmetry as the row, or whether there are several equivalent patterns arising from one another via the symmetry operations. For longer rows whose lengths have various distinct divisors, intermediate cases of partial symmetry can arise.
Figure 7: second stage de Bruijn matrix for width 3 - connected
component of 11
The second component, consisting of 27 nodes, is disconnected from the quiescent state, but is extremely regular. To begin with, the rule of formation is extremely elegant; given any neighborhood containing exactly four live cells, three cells are to be chosen for the new margin so that the overlapping neighborhood also has four live cells; a construction clearly unique to Life . Its connectivity matrix constitutes Figure 7.
Close inspection shows that sections of odd parity---with a single live cell---alternate with sections of even parity---having two live cells---in the ratio of two odd sections to one even section; thus the importance of the height being a multiple of three. Moreover it is pairs of sections which count---the half neighborhoods---so the sequence even-odd, odd-odd, and odd-even must be rigorously followed. Consequently the de Bruijn matrix is imprimitive of degree 3, explaining the magical properties of the number 3.
Further inspection shows that the matrix is the tensor product of a cyclic shift matrix with a full de Bruijn matrix for three states and two stages, which is a consequence of the transversal symmetry. In other words, it doesn't matter which section of a given parity is chosen, but from there on further choices must all be consistent.
Figure 8: typical still lifes for a strip of width 3
To better visualize the still lifes of width three, Figure 8 shows typical samples, one for the component of 00, the other for the component of 11. The former contains three fundamental motifs; horizontal bars which must have castellations whenever they are not surrounded by similar bars; rows of blocks, and extended snakes, using the standard terminology of Life . The motifs may follow in any sequence, and with any phase relative to one another.
Going on to widths of 4 or wider, more and more complicated diagrams are encountered. However, a new phenomonon becomes visible with width 4, which is that the quiescent state may have nontrivial connected components in both the first stage and the second stage. Since the quiescent state is always self-connected, an arbitrary number of additional quiescent states may always be inserted wherever a single one was encountered. Consequently the live cells from any configuration so found continue to form a still life when moved to an environment which is not periodic.
Furthermore, with fewer diagrams, visual presentations for slightly wider strips are still possible.
Figure 9: freestanding strip of width 4
Strips of width 4 show the first nontrivial component of the quiescent state; the second order diagram for this component has 24 nodes, as shown in Figure 9. This is the smallest diagram in which completely freestanding figures occur; they are separable from one another or others by arbitrarily long quiescent intervals, either horizontally or vertically.
Of course, the full de Bruijn diagram for width 4 could also be exhibited; but it isn't since the intricacy of the diagrams increases exponentially with width, making their explicit representation increasingly cumbersome and less visual. Eventually the only feasible representation consists of a table, whose entries list the possible successors of each node in turn.