Factor theory and the unity of opposites

- Calculational presentation of Conway's factor matrix and its properties.
- Non-trivial example of the unity-of-opposites theorem based on the construction of the factor graph of a regular language.
- Worked example showing how the Knuth-Morris-Pratt failure function is a special case of the factor graph.

The theory of factors of a regular language is used to illustrate the unity-of-opposites theorem of Galois connections. Left and right factors of a language are characterised as unions of right- and left-invariant equivalence classes, respectively, and this characterisation is exploited in the construction of the factor graph. The factor graph is a representation of the poset of left factors and, isomorphically by the unity of opposites, the poset of right factors. Two illustrative examples are given, one of which is the failure function used in the Knuth-Morris-Pratt pattern-matching algorithm.