ABSTRACT
We have so far only been concerned with the question of whether or not a language can be recognised by a finite automaton. If it can be, then we have not been interested in how efficiently the job can be done. In this chapter, we shall show that for each recognisable language there is a smallest complete deterministic automaton that recognises it. By ‘smallest’ we simply mean one having the smallest number of states. As we shall prove later in this section, two deterministic automata that recognise the same language each having the smallest possible number of states must be essentially the same; in mathe matical terms, they are isomorphic. This means that with each recognisable language we can associate an automaton that is unique up to isomorphism: this is known as the minimal automaton of the language. This automaton plays a crucial role in Chapters 9-12.
