C. M. Sperberg-McQueen
Founder and principal
Black Mesa Technologies LLC
Technische Universität Darmstadt
Tricolor automata are extensions of finite state automata, intended for the comparison of two regular languages; states and arcs in the automaton are colored to indicate whether they are peculiar to one language or the other, or common to both. Their design represents a simple application to practical purposes of ideas derived from the work of Glushkov and Brzozowski. Examples are given to show how tricolor automata can be used to visualize the intersection, union, and set difference of two languages, and algorithms for constructing them are given.