The Finite State Automata used in this part of the course have been deliberately built to be deterministic in recognition. Image the task of recognising a word, such as [d,i,v,a]. Each arc from a state in such a deterministic recogniser has a unique label. To put it another way, no two arcs from one state can have the same label. This means that when recognising some input, the finite state machine can only go along one route through the network.
Finite State Automata that are non-deterministic in recognition have two or more arcs with the same label emanating from a given state. Any non-deterministic Finite State Automaton can be converted into a corresponding deterministic Finite State Automaton.
Why is determinism important? One reason is because the controller software is much simpler, another reason is that memory requirements are restricted and a final reason is that it may be quicker.
In a non-deterministic Finite State Automaton, the controller has to "remember" the alternative arcs that can be taken. If a route through the network is taken that subsequently blocks (that is, it fails), then the controller has to "unwind" the computation so an alternative route through the network can be taken. This means that the controller has to be constructed in such a way as to include the facility to recover from blocked routes, which in turn means that the controller software has to be more complicated than a corresponding controller for deterministic Finite State Automata. The examples given here were written in Prolog and this is rather like an exception to the general rule. Prolog's in-built search allows for non-determinism without the programmer having to write any extra code, therefore it is no more difficult to write a non-deterministic controller in Prolog than it is to write a deterministic controller. This is not, of course, a disadvantage of Prolog: the non-deterministic search will be much more useful when dealing with more complicated knowledge representations.
A deterministic Finite State Automaton requires less memory than a non-deterministic Finite State Automaton. Given that no alternatives have to be stored, then the search can consume constant memory - that is, it never has to use more memory than that used to traverse the first arc.
A deterministic Finite State Automaton is likely (on average) to be faster than a non-deterministic Finite State Automaton because there are fewer arcs that can be traversed for any given input.
There are quite important issues about what kind of linguistic structures a Finite State Automaton can model. These structures do not occur in the kinds of applications used as examples in this part: word recognition, morphological analysis and spelling correction. The limitations are best seen in relation to the syntactic structure of languages, and this is where this topic will be discussed.