ABSTRACT

In Chapter 2, we looked at various ways of constructing an automaton to recognise a given language. However, we did not get very far. The reason was that automata as we have defined them are quite ‘rigid’: from each state we must have exactly one transition labelled by each element of the input alphabet. This is a strong constraint and restricts our freedom considerably when designing an automaton. To make progress, we need a tool that is easy to use and can help us design automata. This is the role played by the non-deterministic automata we introduce in this chapter. A non-deterministic automaton is exactly like an automaton except that we allow multiple initial states and we impose no restrictions on transitions as long as they are labelled by symbols in the input alphabet. Using such automata, it is often easy, as we shall see, to construct a non-deterministic automaton recognising a given language. However, this would be useless unless we had some way of converting a non-deterministic automaton into a deterministic one recognising the same language. We describe an algorithm that does exactly this. We can therefore add non-deterministic automata to our toolbox for building automata.