Balisage Paper: Tricolor automata

Background

Complex public vocabularies sometimes come in multiple flavors (such as the Transitional and Strict variants of HTML 4.0, or the Archiving, Publishing, and Authoring variants of the Journal Archiving Tag Suite [JATS]); any vocabulary that is used long enough is likely to come in multiple versions (as do HTML, JATS, DocBook, TEI, and others). Since many public vocabularies are designed to be customizable for a given use (and any vocabulary at all may be customized, whether designed for it or not), they will also come in customized and non-customized forms.

Users (and maintainers) of such vocabularies will from time to time wish to understand just how two variants of a vocabulary resemble each other and how they differ from each other. Those preparing a new version of a vocabulary may wish to verify that all documents valid against the old version remain valid, or to see concisely exactly which have been invalidated; those working with a customized vocabulary may wish to understand better just how it differs from the base vocabulary. And so on. In practice, such understanding seems to require the pairwise comparison of corresponding declarations in the two schemas.

We can of course compare the two declarations textually. This sometimes turns out to be less helpful than one might wish. Here is the declaration of the body element in one customization of the TEI (reformatted for legibility):

<!ELEMENT body ((%model.global;)*,
                ((%model.divTop;),
                 (%model.global;|%model.divTop;)*)?,
                (_DUMMY_model.divGenLike,
                 (%model.global;
                 |_DUMMY_model.divGenLike)*)?,
                (((%model.divLike;),
                  (%model.global;
                  |_DUMMY_model.divGenLike)*)+
                 |(_DUMMY_model.div1Like,
                  (%model.global;
                  |_DUMMY_model.divGenLike)*)+
                 |(((%model.common;),
                    (%model.global;)*)+,
                   (((%model.divLike;),
                     (%model.global;
                     |_DUMMY_model.divGenLike)*)+
                    |(_DUMMY_model.div1Like,
                      (%model.global;
                      |_DUMMY_model.divGenLike)*)+)?)),
                ((%model.divBottom;),
                 (%model.global;)*)*)>

And here is another:

<!ELEMENT body ( (%model.global;)*,
                 ( (%model.divTop;), 
                   (%model.global; | %model.divTop;)*
                 )?,                 
                 ( ( (%model.divLike;), 
                     (%model.global;)* )+ 
                 | ( ( (%model.common;), 
                       (%model.global;)* )+,
                     ( ( (%model.divLike;), 
                         (%model.global;)* )+ )? ) 
                 ),
                 ( (%model.divBottom;), 
                   (%model.global;)*
                 )*
               ) >

So many details are hidden behind the parameter entities (or in a Relax NG schema behind the named patterns, or in an XSD schema behind the named types, type inheritance, and named model groups) that it is difficult to see, from the textual form of the declaration, just where the two content models are the same and where they differ. If we expand the content models, with content models this complex, the situation does not become better.

Drawing a finite-state automaton (FSA) of a content model can sometimes make the structure clearer (although in the case of complex models like these, there are so many states in the automata that careful study may be needed). Here is the first declaration, in FSA form:

Figure 1

Here is the FSA for the second declaration:

Figure 2

The FSAs may be easier to understand, in some ways, than the textual declarations, but comparing them does not seem materially easier. Can we do better?^[1]

Desiderata

Informally, the problem is: given two regular expressions A and B, draw a circle-and-arrow diagram which allows the user to see as clearly as possible what the FSAs look like for languages L(A), L(B), L(A∩B), and L(A∪B).

This is informal because as clearly as possible implies some sort of optimization, and we don't have a clear notion of optimality. Intuitively,

We know from automata theory that these desiderata may conflict: Glushkov automata are often not minimal, and determinizing an NFSA sometimes adds states. In the general case, then, there may be multiple forms of optimality based on different priorities among these three desiderata.

The Glushkov Property

The term Glushkov property is not standard, so it should be explained. The Russian mathematician V.M. Glushkov described an algorithm for making an FSA from any regular expression, with n+1 states, where the regular expression contains n letters [Glushkov 1961]. (Or in SGML/XML terms, where the content model contains n primitive content tokens — #PCDATA or a generic identifier.) Anne Brüggemann-Klein and D. Wood pointed out that the ambiguity rule of SGML amounted to this: the Glushkov Automaton built from a content model must be deterministic [Brüggemann-Klein 1993a], [Brüggemann-Klein 1993b], [Brüggemann-Klein/Wood 1998]. If it's not, there is what SGML describes as an ambiguity error.

Now, since in a Glushkov automaton we have one state per letter in the regex, we can simply say the states of the Glushkov automaton are the letters (i.e. the letter tokens) in the regex. So each state is a token in the regex. And every incoming transition to a state q is labeled with the type of q. So the content model (a, (b|c)*, d) has five states: one start state and one state for each of the tokens a, b, c, and d. There is a transition from a to b, labeled b, and a transition from a to c, labeled c. And (because the choice of b and c has an asterisk as its occurrence indicator), there is also a transition from a to d, labeled d. There are also transitions from b and c to b and c, labeled b and c. And from the same two states there is a transition to d, labeled d.

Figure 3

Note that every incoming transition to b carries the same label, namely b, and similarly for nodes c and d.

Since in a Glushkov automaton every incoming transition to a state q is labeled with the type of q, it follows that when we draw Glushkov automata, we can label the states and leave the transitions unlabeled.

Figure 4

We know what label a transition has, because we can read it from the target state. Some readers may find that Glushkov automata remind them a bit of Moore machines. In each cases each state in the automaton is associated with a single symbol: an output symbol, in the case of a Moore machine, and an input symbol, in the case of the Glushkov automaton.

In general, however, FSA edges may be labeled with more than one symbol. A minimal FSA for the expression (a, (b|c)*, d) will have only three states, not five:

The FSA will have the following arcs:

Figure 5

The cycle on state q₁ is labeled b | c; the alternative is to have two arcs, one for each label, but the figure is less cluttered if there is only one arc between any two states; that arc may be labeled with a set of symbols, not a single symbol.

We say that such an FSA has the Glushkov property if for any state q, all of q's incoming arcs have the same set of labels. Thus (just as for a Glushkov automaton), we can label each state q with the set of symbols that can reach q from some other state (more formally: the set of symbols which can appear as the last symbol in a sequence that starts at the start state and ends at q).

Note that all Glushkov automata have the Glushkov property, but not all automata with the Glushkov property are Glushkov automata. The two FSAs for customizations of the TEI body element shown above, for example, have the Glushkov property, but each or-group in the content model is represented by a single state, rather than one state for each primitive content token in the or-group. This dramatically reduces the size and complexity of the FSA for some content models, and makes the FSA more legible. Just as with any FSA, if any two equivalent states in a Glushkov automaton are merged, the resulting FSA will recognize the same language as the original. To retain the Glushkov property, however, we must impose the additional constraint that the two states must not only be equivalent (both in or both outside the set of final states, and both with transitions to the same set of following states), but also have incoming transitions from the same set of preceding states.

The reason we want the Glushkov property is that it makes the drawings easier to draw and (so it seems) easier to understand. This may be related to the apparently common view that Moore machines are easier to understand than Mealy machines, even though they may have more states.

The tainted-string approach

The tainted-string approach draws an FSA in which we can traverse from white states to red or blue states, but not vice versa: once we are in a red state we are always thereafter in red states, and similarly for blue states. (This might be called the McCarthy principle: once a red, always a red.)

For example, let A = (a|x)*, z:

Figure 6

Let B = (b|x)+, z.

Figure 7

A simple algorithm for translating from content models to tricolor automata will produce something like the following:

Figure 8

There are two problems with this, however: First, in state q₀, symbol x is non-deterministic: it can go to any of three places. If we want blue and red to mean B-only and A-only, we don't want x going to red or blue states. One way to fix this would be to label the arcs and not the states:

Figure 9

It is perhaps only a subjective view, but speaking for myself I find that harder to read, and in more complicated cases — as illustrated by almost any content model from a real public vocabulary — it's even worse.

And the automaton has now lost the Glushkov property: the node labeled a|x has two incoming arcs labeled a and a third incoming arc labeled a|x; the node labeled b|x has similarly inconsistent labels on incoming arcs. We can regain the Glushkov property and get back to labeling states by adding new states:

Figure 10

This is a reasonably clear graph. It's deterministic, and it has the Glushkov property, and it is the smallest FSA I have found that has those properties. Its treatment of the three final states illustrates very nicely the tainted-string approach: we cannot use a single state for z, because the taint approach says that from a red state, only red states are reachable.

The color-filter approach

If we relax the McCarthy principle and allow transitions from red or blue states to white states, in order to reduce the size of the automaton, the first cut looks like this:

Figure 11

However, this is again non-deterministic. What I think we want is something like this:

Figure 12

Note that this example shows that in the color-filter approach, coloring the arcs is necessary, because q₀ → z is only legal in L(A)); in the tainted-string approach, arcs need not be colored.

A complication

Consider the two expressions A = (a|x)*, z and B = (b|x)*, z?. (That is, A is as above, and B is modified by making the closing z optional.)

The diagrams we want will be very similar to the final versions of the tainted-string and color-filter diagrams shown above, but they must change to reflect the fact that the states b, x, and b | x are all now final states in expression B.

This forces us into a choice. In the examples given above, both of the following rules hold true:

This example seems to allow us to retain at most one of these generalizations.

If we retain the first and abandon the second, we will end up with a diagram like this for the tainted-string approach:

Figure 13

For the color-filter approach, we get:

Figure 14

Note that in both cases, we have lost determinism: an initial x goes either to the white state x or the blue final state b | x.

We can retain determinism if we adopt the convention that a white state can be marked final either in black (as above), or in red or blue. In the latter case, it means that the state is a final state for L(A) but not L(B), or vice versa.

On this principle, the tainted-string approach gives us a diagram like this:

Figure 15

And the color-filter approach produces:

Figure 16

At the beginning of this section, I said we must choose between determinism and the rule that finality of a state is independent of color. Actually, we do not have a real choice, as should be clear from consideration of the pair A = (a|x)*, z? and B = (b|x)*, z. Here the initial state is final in A, but not in B. Unless we want to assume multiple possible initial states (and rewrite as much of standard automata theory as necessary in order to deal with the change), we must have a way to indicate that a state may be visited by strings in either L(A) or L(B), but is final in only one of those languages.

Interpreting the diagrams

So, what does this circle-and-arrow diagram mean? I believe it describes, concisely, how to construct strings in:

Note that if we ignore colors entirely, the circles-and-arrows diagram describes an FSA for an expression something like (a | b | x)*, z.^[3] This is not the union of L(A) and L(B) (it's larger), but it is close to what some document designers (including me) would probably write, if someone asked for a grammar that would accept both A documents and B documents and also would look like a rational document grammar. In some real-world cases, effective content models like ((a|x)*, z) and ((b|x)+, z) arise as expansions of ((%some-element-class;)*, z) and ((%some-element-class;)+, z): the two effective models differ because (a) the two versions have customized the some-element-class class differently and (b) vocabulary B has required at least one occurrence of an element in the class (or, possibly, A has made it optional). The natural union schema for A and B in this case would define the class some-element-class to include a, b, and x (the union of its members in vocabularies A and B), and define the content model as ((%some-element-class;)*, z), which would expand to (a | b | x)*, z.

The one catch is that this is not, strictly speaking, an FSA. The characteristic of an FSA is that the only memory it has is the identity of its current state. When a string ends, we are allowed to ask Is the current state a member of the set of final states? and that's it. Keeping track of what colors we have seen along the way requires memory that goes beyond keeping track of the current state.

It's clear, however, that from such a graph we can readily construct an FSA for the first four of the languages identified above, by dropping out the states and arcs that are outlawed in the rule for that language. For the last two languages listed, it may not be straightforward to construct a free-standing FSA; that it is possible is a straightforward fact of automata theory.

Formal definition

We are now in a position to define a tricolor automaton more formally.

A tricolor automaton is a triple (A, Χ, Φ), where

Given the intended uses of tricolor automata as outlined in the preceding section, some possible chromatic functions will make no sense in practical applications. Arcs connecting red and blue states, red arcs incident to blue states, blue arcs incident to red states, white arcs connecting pairs of red or pairs of blue states, can play no role in the strings of any of the languages of particular interest. Similarly if a red state is mapped by Φ to any color but red, the conventional implication is that the state is final in B, but the state cannot be reached by any string in L(B), so the mapping in Φ has no effect on any language except that of the base FSA. (And analogously for any blue states mapped by Φ to any color but blue.)

In practical applications, therefore, the chromatic functions Χ and Φ will normally obey the consistency constraints that

The tainted-string approach

The simplest case uses the tainted-string approach. Here, we identify states based on the strict identity of the triple. We can describe the algorithm as follows. We keep a list of triples seen so far, and mark each triple when it is processed.

In what follows, it will be convenient to define the derivative of a triple (s₁, DA, DB) with respect to some input symbol s as the triple (s, DA′, DB′), where DA′ is the result of simplifying the derivative of E with respect to s and DB′ is the result of simplifying the derivative of DB with respect to s.

The process is guaranteed to terminate, because the number of non-equivalent DA and DB which can be generated from A and B is finite.

The resulting tricolor automaton and its underlying finite state automaton A can be described thus:

The logic of the coloring scheme is this. Any state in which DA = ∅ is outside the language of A, so it's B-only, and any state with DB = ∅ is outside the language of B, so it's A-only. We color them blue and red, respectively. Any state with neither DA nor DB = ∅ is at least potentially in the intersection, so it's white. And any state with DA = DB = ∅ is of no interest so we drop it.

Since any state with DA ≠ ∅ is colored white or red, any path restricted to white and red states and arcs

A similar technique can be used to create a tricolor automaton from two FSAs instead of two regular expressions. It resembles the usual algorithm for calculating an FSA for the intersection of two languages recognized by FSAs, but its states are again triples, which consist of an input symbol, a state from the first FSA (or a flag indicating that there is no applicable state), and a state from the second FSA (or a not-applicable flag).

An example

The algorithm can be illustrated by applying it to the example used above.

At the outset, our list of triples has just one entry, for the start state:

For the two expressions A and B, the derivatives with respect to the symbols of the alphabet are as follows:

Let's give the name B′ to the expression (b|x)*,z, for brevity. From these, we can calculate the derivatives of triple q₀: Each of these is new and is added to the list:

The fragment of the automaton thus far constructed is this:

Figure 17

We now take the derivatives of each of these new states:

At this point, we've added several new states (q₅ through q₈), and the graph looks like this:

Figure 18

Calculating derivatives for the new states produces no new states, but some new arcs:

The result of adding the new arcs is shown below.

Figure 19

Or, getting rid of the bookkeeping details:

Figure 20

This is almost but not quite the same as the last graph shown in the introductory section on the tainted-string approach above. By the desiderata mentioned at the outset, it is almost, but not quite, as good: it has the same number of states, but more arcs.

The color-filters approach

This approach is just like the tainted-string approach, with just one difference: after construction of the automaton, we search for two states of the form (s, DA, DB) and (s DA, ∅) or (s, DA, DB) and (s ∅, DB). Each such pair we find is merged by keeping the first (full) form and dropping the other.

In our example, this leads to the merger of states q₃ = (x, A, B′), q₅ = (x, A, ∅), and q₆ = (x, ∅, B′). It also leads to the merger of the three z-states q₄, q₈, and q₇.

Figure 21

Or, without 5-tuples:

Figure 22

This is isomorphic to the graph shown above in the introduction to the color-filter approach.