ABSTRACT
Non-deterministic and deterministic automata have something in common: both types of machines can only change state as a response to reading an input symbol. In the case of non-deterministic automata, a state and an input symbol lead to a set of possible states. The class of e-automata, introduced in this chapter, can change state spontaneously without any input symbol being read. Although this sounds like a very powerful feature, we shall show that every non-deterministic automaton with e-transitions can be converted into a non-deterministic automaton without e-transitions that recognises the same language. Armed with e-automata, we can construct automata to recognise all kinds of languages with great ease. Our main application of e-automata will be in Section 5.3.
