Nondeterministic Finite Automaton (NFA)

In a nondeterministic finite automaton (NFA),for each state there can be zero, one, two, or more transitions Corresponding to a particular symbol. If NFA gets to state with more than one possible transition corresponding to the input symbol, we say it branches. If NFA gets to a state where there is no valid transition, then that branch dies.


NFA Acceptance

An NFA accepts the input string if there exists some choice of transitions that leads to ending in an accept state.
Thus, one accepting branch is enough for the overall NFA to accept, but every branch must reject for the overall NFA to reject. This is a model of computation. We write DFA to specify a deterministic finite automaton (the one defined earlier). If type doesn’t matter, we now just write FA.

let’s take examples for more clear:

\begin{figure}\begin{center} \begin{tabular}{ccc} \psfig{figure=figs/nfa2.eps,wi... .../nfa.eps,width=1.9in} \\ (a) & & (b) \\ \end{tabular}\end{center} \end{figure}

In above figure(a) An nondeterministic finite automaton (NFA) is a state machine that reads an input string and decides whether to accept it. (b) A graphical depiction of an NFA.

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 $ 1$‘s. The initial state is designated by an inward arrow that has no source vertex, as shown pointing into state $ a$ 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 $ 1$ 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 $ c$ (the arrow from $ c$ to $ b$ actually corresponds to two directed edges, one for 0 and the other for $ 1$). There are also edges designated with a special $ \epsilon$ symbol. If a state has an outgoing $ \epsilon$, the state may immediately transition along the edge without reading another symbol. This may be iterated any number of times, for any outgoing $ \epsilon$ 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 $ \epsilon$transitions. There is no sensor that indicates which state is actually chosen.

The interpretation often given in the theory of computation is that when there are multiple choices, the machine clones itself and one copy runs each choice. It is like having multiple universes in which each different possible action of nature is occurring simultaneously. If there are no outgoing edges for a certain combination of state and input, then the clone dies. Any states that are depicted with a double boundary, such as state $ a$ in Figure 11.8, are called accept states. When the input string ends, the NFA is said to accept the input string if there exists at least one alternate universe in which the final machine state is an accept state.

The formulation usually given for NFAs seems very close to Formulation 2.1 for discrete feasible planning. Here is a typical NFA formulation [891], which formalizes the ideas depicted in Figure 11.8:

  1. A finite state space $ X$.
  2. A finite alphabet$ \Sigma$ which represents the possible input symbols. Let $ \Sigma_\epsilon = \Sigma \cup \{\epsilon\}$.
  3. A transition function, $ \delta : X \times \Sigma_\epsilon \rightarrow {\rm pow}(X)$. For each state and symbol, a set of outgoing edges is specified by indicating the states that are reached.
  4. A start state$ x_0 \in X$.
  5. A set $ A \subseteq X$ of accept states.


For example all we need about an FA that accepts { a } is the following regardless of the alphabet (whether be it { a } , { a , b } or any other) .

This is so to say the essence of such an FA. But it is not DFA. A DFA that accepts { a } would need more states and transitions as you can see below for example.

Without those extra state and transitions it is not a DFA if the alphabet is { a , b } .
To avoid those redundant states and transitions and to make modeling easier we use finite automata called nondeterministic finite automata (abbreviated as NFA) . Below we are going to formally define nondeterministic finite automata (abbreviated as NFS) and see some examples. As we are going to see later, for any NFA there is a DFA which accepts the same language and vice versa.

NFAs are quite similar to DFAs. The only difference is in the transition function. NFAs do not necessarily go to a unique next state. An NFA may not go to any state from the current state on reading an input symbol or it may select one of several states nondeterministically (e.g. by throwing a die) as its next state.

Definition of nondeterministic finite automaton

Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to 2Q ,   let q0 be a state in Q and let A be a subset of Q. We call the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states.
Then a nondeterministic finite automaton is a 5-tuple < Q , , q0 , , A >

Notes on the definition

  1. As in the case of DFA the set Q in the above definition is simply a set with a finite number of elements. Its elements can be interpreted as a state that the system (automaton) is in.
  2. The transition function is also called a next state function . Unlike DFAs an NFA moves into one of the states given by (q, a) if it receives the input symbol a while in state q. Which one of the states in (q, a) to select is determined nondeterministically.
  3. Note that is a function. Thus for each state q of Q and for each symbol a of   (q, a) must be specified. But it can be the empty set, in which case the NFA aborts its operation.
  4. As in the case of DFA the accepting states are used to distinguish sequences of inputs given to the finite automaton. If the finite automaton is in an accepting state when the input ends i.e. ceases to come, the sequence of input symbols given to the finite automaton is “accepted”. Otherwise it is not accepted.
  5. Note that any DFA is also a NFA.



Examples of NFA

Example 1: Q = { 0, 1 }, = { a }, A = { 1 }, the initial state is 0 and is as shown in the following table.

State (q) Input (a) Next State ( (q, a) )
0 a { 1 }
1 a

A state transition diagram for this finite automaton is given below.

If the alphabet is changed to { a, b } in stead of { a }, this is still an NFA that accepts { a } .

Example 2: Q = { 0, 1, 2 }, = { a, b }, A = { 2 }, the initial state is 0 and is as shown in the following table.

State (q) Input (a) Next State ( (q, a) )
0 a { 1 , 2 }
0 b
1 a
1 b { 2 }
2 a
2 b

Note that for each state there are two rows in the table for corresponding to the symbols a and b, while in the Example 1 there is only one row for each state.

A state transition diagram for this finite automaton is given below.

Operation of NFA

Let us see how an automaton operates when some inputs are applied to it. As an example let us consider the automaton of Example 2 above.
Initially it is in state 0. When it reads the symbol a, it moves to either state 1 or state 2. Since the state 2 is the accepting state, if it moves to state 2 and no more inputs are given, then it stays in the accepting state. We say that this automaton accepts the string a. If on the other hand it moves to state 1 after reading a, if the next input is b and if no more inputs are given, then it goes to state 2 and remains there. Thus the string ab is also accepted by this NFA. If any other strings are given to this NFA, it does not accept any of them.

Let us now define the function * and then formalize the concepts of acceptance of strings and languages by NFA.