Non- Deterministic Fenite Automata

Non-deterministic finite automata (NFA) have transition functions which may assign several or no states to a given state and an input symbol. They accept a word if there is any possible transition from the one of initial states to one of the final states. It is important to note that although NFAs have a non-determistic transition function, it can always be determined whether or not a word belongs to its language (). 

An interesting connection lies between the ideas of this chapter and the theory of finite automata, which is part of the theory of computation (see [462,891]). In Section 2.1, it was mentioned that determining whether there exists some string that is accepted by a DFA is equivalent to a discrete feasible planning problem. If unpredictability is introduced into the model, then a nondeterministic finite automaton (NFA) is obtained, as depicted in Figure 11.8. This represents one of the simplest examples of nondeterminism in theoretical computer science. Such nondeterministic models serve as a powerful tool for defining models of computation and their associated complexity classes. It turns out that these models give rise to interesting examples of information spaces.  

An NFA is typically described using a directed graph as shown in Figure 11.8b, and is considered as a special kind of finite state machine. Each vertex of the graph represents a state, and edges represent possible transitions. An input string of finite length is read by the machine. Typically, the input string is a binary sequence of 0's and 's. The initial state is designated by an inward arrow that has no source vertex, as shown pointing into state in Figure 11.8b. The machine starts in this state and reads the first symbol of the input string. Based on its value, it makes appropriate transitions. For a DFA, the next state must be specified for each of the two inputs 0 and from each state. From a state in an NFA, there may be any number of outgoing edges (including zero) that represent the response to a single symbol. For example, there are two outgoing edges if 0 is read from state (the arrow from to actually corresponds to two directed edges, one for 0 and the other for ). There are also edges designated with a special symbol. If a state has an outgoing , the state may immediately transition along the edge without reading another symbol. This may be iterated any number of times, for any outgoing edges that may be encountered, without reading the next input symbol. The nondeterminism arises from the fact that there are multiple choices for possible next states due to multiple edges for the same input and transitions. There is no sensor that indicates which state is actually chosen.