ABSTRACT
In Theorem 9.4.3, we proved that a language is recognisable precisely when its syntactic monoid is finite. This result opened the door to an algebraic approach to recognisable languages. In Chapter 11, we showed that the syntactic monoid is an important tool in studying recognisable languages when we characterised star-free languages in terms of their syntactic monoids. However, we showed in Section 10.3 that not every finite monoid is a syntactic monoid, and that different languages can have the same syntactic monoid. What these results point us toward is this: there is a correspondence, not between individual finite monoids and individual recognisable languages, but between families of monoids and families of languages. The aim of this chapter is to explain what this means and to prove the theorem on which it depends: the Variety Theorem of Eilenberg and Schiitzenberger. This theorem provides a framework for thinking about finite monoids and recognisable languages.
