Finite Automata

Definition of Nondeterministic Finite Automata

Subjects to be Learned


In the previous section we have seen DFAs that accept some simple languages such as , {} , and { a }. As you might have noticed, those DFAs have states and transitions which do not contribute to accepting strings and languages. 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.

Test Your Understanding of Definition of NFA

Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
There are two sets of questions.

The following notations are used in the questions:

   : \delta

Next -- Language Accepted by NFA

Back to Study Schedule

Back to Table of Contents