ABSTRACT
In this chapter, we take the first steps in describing an algebraic method for answering questions about recognisable languages. The basic idea is simple. Consider a complete deterministic automaton. Each input string to the au tomaton defines a function from the set of states to itself. Although there are infinitely many input strings, there can only be a finite number of distinct functions that arise in this way because our machine has only a finite number of states. Thus the set of input strings leads to a finite set of functions defined on the set of states. This set of functions has an additional property: the composition of any two of them is again in the set. Because composition of functions is associative, we therefore obtain a set equipped with an associative binary operation. Such a set is called a ‘semigroup,’ and because it has only finitely many elements, the semigroup in question is a ‘finite semigroup.’ Thus with each automaton we can associate a finite semigroup. Now suppose we have a recognisable language. This is accepted by an essentially unique mini mal automaton by Theorem 7.4.2 and, by the process above, we can associate a finite semigroup with this machine. It follows that with each recognisable language we can associate a finite semigroup. We shall see in Chapters 9-12 that this semigroup can be used to obtain important information about the language in question.
