ABSTRACT
In the last chapter, we associated two monoids with an automaton: the transi tion monoid and the monoid of representatives. The algebraic ideas described in this chapter will enable us to prove that these two monoids are essentially the same or ‘isomorphic.’ We are not just interested in these monoids for their own sake, they can help us to understand the properties of recognisable languages by means of the following idea. Given a recognisable language, we can construct its minimal automaton A, which is, as we have seen, essentially unique. The transition monoid of A might therefore be expected to have some special significance, and it does. With any language whatsoever we can asso ciate a monoid called the syntactic monoid of the language. This monoid is finite precisely when the language is recognisable, in which event the syntactic monoid is isomorphic to the transition monoid of the minimal automaton asso ciated with the language. With each recognisable language, therefore, we can associate a finite monoid and this monoid can be explicitly calculated using the mininal automaton of the language. Encoded into the algebraic structure of this monoid is information about the language.
