Theory of Computation – Nondeterministic Finite Automata (NFA) – Definitions, Programming, Examples

Nondeterministic means choice of moves for automata. In non-deterministic finite automata we are allowed a set of possible moves. The definition of nondeterministic automata is similar to that of deterministic finite automata but with one difference, the transition function. A nondeterministic finite automata is s 5-tuple ( Q, Σ, δ, F q0), where
Q: is a non-empty finite set of states present in the finite control.
Σ: is a non-empty finite set of input symbols which can be passed on to the finite state machine
q0: is a starting state, q0 ϵ Q
F: is a non-empty set of final states or accepting states, set of final states is a subset of Q.
δ: is a function called transition function that takes two arguments a state and a input symbol and it returns a subset of Q that is,
Q x (Σ U {є})->2Q
2Q is the power set of Q (the set of subsets of Q).

The language accepted by a NFA is regular just as in case of a DFA . There are some languages that cannot be represented by a DFA but can be represented as an NFA for example (11 + 110)*0 cannot be represented by a DFA. The non-deterministic finite automata can be thought of as a machine making decisions. The given expression is shown in the form an automaton in the figure. There are two possible moves from the start state on input 1. Nondeterminism means that the behavior of the language is unpredictable. On a given input we can for a state we may have choice of making the move to more than one state unlike in deterministic finite automata where transition to only a single state is permitted for a given input symbol.

The transition graph for a NFA is constructed in the same way as a DFA. For the transition table there may be multiple states in a column for a given state. The transition diagram for the NFA for (11 + 110)*0 would be :
TOC_NFA_img1

Question 1: Design a NFA for the following language:

  1. L = (ab)* (ba)* U aa*

  2. L = all strings over {0, 1} that have at least two consecutive 0’s or 1’s.

View Answer

Answer:
  1. TOC_NFA_img2
  2. TOC_NFA_img3

Question 2: Design a NFA and a DFA for the language L = (ab U aba)*.
View Answer


The DFA for the language will be:
TOC_NFA_img4

and the NFA would be :
TOC_NFA_img5

Question 3: Write a program to simulate a NFA. Run the code for the NFA (11 + 110)*0.

Answer:
A NFA can be simulated in many ways. The approach in the following program is to store all the possible current state for a given input symbol and after the final input test if the NFA ends up in a final state.
Here is source code of the C++ Program to simulate a nondeterministic finite automaton. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <stdlib.h>
  5. using namespace std;
  6.  
  7. class Transition{
  8.     public:
  9.     string str;
  10.     int cnt;
  11.     string * list;
  12.  
  13.     // a function to tokenize the string and store it in the list
  14.     void strTokenize() {
  15.         comma ();
  16.         char *cstr = new char[str.length() + 1];
  17.         strcpy(cstr, str.c_str());
  18.         char *p = strtok(cstr, ",");// in strtok() first parameter has t0 be a character array
  19.         int i = 0;
  20.         list = new string[cnt];
  21.         // tokenize the string and create a list of states for that symbol
  22.         while (p != 0) {
  23.             list[i] = p;
  24.             i++;
  25.             p = strtok(NULL, ",");
  26.         }
  27.     }
  28.  
  29.     void showList(){
  30.         for (int i=0; i < cnt; i++)
  31.             cout << list[i] << " ";
  32.     }
  33.  
  34.     private:
  35.     // function to count the comma (',') in the entered set of states
  36.     void comma() {
  37.         cnt = 1;
  38. 	size_t found = str.find(',');
  39.         while (found != string::npos) {
  40.             cnt++;
  41.             found = str.find(',', found + 1);
  42.     	}
  43.      }
  44.  
  45. };
  46.  
  47. int main() {
  48.     Transition **trans;
  49.     string *states, *final, str, input, temp[nos], current[nos];
  50.     char *alf;
  51.     int nos, nofs, noa, i, j, k, x, y, z, f, flag, cnt, temp_last, curr_last;
  52.  
  53.     cout << "Enter the total number of states and the "
  54.     << "number of final states :\n";
  55.     cin >> nos >> nofs;
  56.     states = new string[nos];
  57.     final = new string[nofs];
  58.     cout << "Enter the states (enter the start state first)\n";
  59.     for (i = 0; i < nos; i++)
  60.         cin >> states[i];
  61. 	cout << "Enter the final states\n";
  62.     for (i = 0; i < nofs; i++)
  63.         cin >> final[i];
  64.  
  65.     cout << "Enter the number of symbols in the alphabet : ";
  66.     cin >> noa;
  67.     alf = new char[noa];
  68.     cout << "Enter the symbols for the alphabet:\n";
  69.     for (i = 0; i < noa; i++)
  70.         cin >> alf[i];
  71.  
  72.     // allocating space for the transition table
  73.     trans = new Transition*[nos];
  74.     for (j = 0; j < nos; j++)
  75.         trans[j] = new Transition[noa];
  76.  
  77.     // retrieving the information for transition table
  78.     cout << "Enter the information for the transition table"
  79.          << " (enter t when no move is possible from the given state) :\n";
  80.     for (i = 0; i < nos; i++) {
  81. 	cout << "Write the transitions for state " << states[i] << endl;
  82.         for (j = 0; j < noa; j++){
  83.        	    cout << "On input symbol " << alf[j] << ": ";
  84. 	    cin >> trans[i][j].str;
  85.             trans[i][j].strTokenize();
  86. 	}
  87.     }
  88.     cout << endl << "the transition table entered by you is :\n";
  89.     for (i = 0; i < nos; i++) {
  90.         for (j = 0; j < noa; j++) {
  91.             trans[i][j].showList();
  92.             cout << "\t\t";
  93.         }
  94.         cout<<endl;
  95.     }
  96.  
  97.     // this array of strings will contain the states that are currently being considered
  98.     while (true) {
  99.         cout << "\nEnter the input string (enter exit to stop the program) : ";
  100.         cin >> input;
  101.         if (input == "exit")
  102.             exit(0);
  103.  
  104.         curr_last = 0;
  105.         current[curr_last] = states[0];// initialising the current state with the start state
  106.         for (i = 0; i < input.length(); i++){
  107.         // getting the index of the alphabet symbol
  108.             for (j = 0; j < noa; j++)
  109.                 if (alf[j] == input[i])
  110.                     break;
  111.  
  112. 	    // processing of the input string by the NFA
  113.  
  114.         /*  first for an input we will pop off from the current
  115.             then we will scan all the transitions from that state for the input symbol
  116.             then we will add these transition to the temp variable if it was not previously present
  117.             finally we will replace the values in current with the values in temp
  118.             curr_last has to be updated accordingly
  119.             index of the alphabet symbol is stored in j
  120.             Transition is T[current_state_being scanned][j]
  121.         */
  122.  
  123.         // to get the current states number scan states[k]
  124.  
  125.             temp_last = 0;
  126.  
  127. 	    for (k = 0; k <= curr_last; k++) { //loop for scanning the transitions from every state in current
  128.                 if (current[k] == "t")
  129.                     continue;
  130. 	        for (x = 0; x < nos; x++)
  131.                     if (states[x] == current[k])
  132.                         break;
  133.                 cnt = trans[x][j].cnt;
  134.                 for (y = 0; y < cnt; y++){// iterating the list of transitions
  135.                     str = trans[x][j].list[y];
  136.                     flag = 0;
  137.                     for (z = 0; z < temp_last; z++){ // checking whether the state is already present in the temp[]
  138.                         if (str == "t") {
  139.                             flag = 1;
  140.                             break;
  141.                         }
  142.                         if (temp[z] == str) {
  143.                             flag = 1;
  144.                             break;
  145.                         }
  146.                     }
  147.                     if (flag == 0)
  148.                         temp[temp_last++] = str;
  149.                 }
  150.                 // updating the current and curr_last
  151.  
  152.             }
  153.  
  154.             for (y = 0; y <= temp_last; y++)
  155.                 current[y] = temp[y];
  156.             curr_last = temp_last - 1; // as the last increment was not required
  157.         }
  158.  
  159.         f = 0;
  160.         // loop checking for acceptance
  161.         for (i = 0; i <= curr_last; i++) {
  162.             for(j = 0; j < nofs; j++)
  163.                 if (final[j] == current[i]) {
  164.                     cout<<"\n----The string has been accepted----\n";
  165.                     f = 1;
  166.                     break;
  167.                 }
  168.             if (f == 1) break;
  169.         }
  170.  
  171.     if (f == 0)
  172.         cout<<"\n----The string has been rejected----\n";
  173. }
  174. return 0;
  175. }

Output

Enter the total number of states and the number of final states
5
1
Enter the states (enter the start state first)
q0
q1
q2
q3 
q4
Enter the final states
q4
Enter the number of symbols in the alphabet : 2
Enter the symbols for the alphabet:
0
1
Enter the information for the transition table (enter t when no move is possible from the given state):
Write the transitions for state q0
On input symbol 0: q4
On input symbol 1: q1,q2
Write the transitions for state q1
On input symbol 0: t 
On input symbol 1: q0
Write the transitions for state q2
On input symbol 0: t
On input symbol 1: q3 
Write the transitions for state q3
On input symbol 0: q0
On input symbol 1: t
Write the transitions for state q4
On input symbol 0: t
On input symbol 1: t
 
the transition table entered by you is :
q4 		q1 q2 		
t 		q0 		
t 		q3 		
q0 		t 		
t 		t 		
 
Enter the input string (enter exit to stop the program) : 1101101
 
----The string has been rejected----
 
Enter the input string (enter exit to stop the program) : 10101
 
----The string has been rejected----
 
Enter the input string (enter exit to stop the program) : 1101110
 
----The string has been rejected----
 
Enter the input string (enter exit to stop the program) : 1101100
 
----The string has been accepted----
 
Enter the input string (enter exit to stop the program) : 11110
 
----The string has been accepted----
 
Enter the input string (enter exit to stop the program) : 111100
 
----The string has been accepted----
 
Enter the input string (enter exit to stop the program) : exit

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.

Subscribe Newsletter & Posts
About

Manish Bhojasia, a technology veteran with 17+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below.


Sanfoundry Training Center of Excellence (CoE)

Manish Bhojasia, a technology veteran with 17+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below.

Subscribe Newsletter & Posts
Follow Manish & Sanfoundry