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 :
Question 1: Design a NFA for the following language:
- L = (ab)* (ba)* U aa*
- L = all strings over {0, 1} that have at least two consecutive 0’s or 1’s.
Question 2: Design a NFA and a DFA for the language L = (ab U aba)*.
View Answer
and the NFA would be :
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.
#include <iostream>
#include <string>
#include <cstring>
#include <stdlib.h>
using namespace std;
class Transition{
public:
string str;
int cnt;
string * list;
// a function to tokenize the string and store it in the list
void strTokenize() {
comma ();
char *cstr = new char[str.length() + 1];
strcpy(cstr, str.c_str());
char *p = strtok(cstr, ",");// in strtok() first parameter has t0 be a character array
int i = 0;
list = new string[cnt];
// tokenize the string and create a list of states for that symbol
while (p != 0) {
list[i] = p;
i++;
p = strtok(NULL, ",");
}
}
void showList(){
for (int i=0; i < cnt; i++)
cout << list[i] << " ";
}
private:
// function to count the comma (',') in the entered set of states
void comma() {
cnt = 1;
size_t found = str.find(',');
while (found != string::npos) {
cnt++;
found = str.find(',', found + 1);
}
}
};
int main() {
Transition **trans;
string *states, *final, str, input, temp[nos], current[nos];
char *alf;
int nos, nofs, noa, i, j, k, x, y, z, f, flag, cnt, temp_last, curr_last;
cout << "Enter the total number of states and the "
<< "number of final states :\n";
cin >> nos >> nofs;
states = new string[nos];
final = new string[nofs];
cout << "Enter the states (enter the start state first)\n";
for (i = 0; i < nos; i++)
cin >> states[i];
cout << "Enter the final states\n";
for (i = 0; i < nofs; i++)
cin >> final[i];
cout << "Enter the number of symbols in the alphabet : ";
cin >> noa;
alf = new char[noa];
cout << "Enter the symbols for the alphabet:\n";
for (i = 0; i < noa; i++)
cin >> alf[i];
// allocating space for the transition table
trans = new Transition*[nos];
for (j = 0; j < nos; j++)
trans[j] = new Transition[noa];
// retrieving the information for transition table
cout << "Enter the information for the transition table"
<< " (enter t when no move is possible from the given state) :\n";
for (i = 0; i < nos; i++) {
cout << "Write the transitions for state " << states[i] << endl;
for (j = 0; j < noa; j++){
cout << "On input symbol " << alf[j] << ": ";
cin >> trans[i][j].str;
trans[i][j].strTokenize();
}
}
cout << endl << "the transition table entered by you is :\n";
for (i = 0; i < nos; i++) {
for (j = 0; j < noa; j++) {
trans[i][j].showList();
cout << "\t\t";
}
cout<<endl;
}
// this array of strings will contain the states that are currently being considered
while (true) {
cout << "\nEnter the input string (enter exit to stop the program) : ";
cin >> input;
if (input == "exit")
exit(0);
curr_last = 0;
current[curr_last] = states[0];// initialising the current state with the start state
for (i = 0; i < input.length(); i++){
// getting the index of the alphabet symbol
for (j = 0; j < noa; j++)
if (alf[j] == input[i])
break;
// processing of the input string by the NFA
/* first for an input we will pop off from the current
then we will scan all the transitions from that state for the input symbol
then we will add these transition to the temp variable if it was not previously present
finally we will replace the values in current with the values in temp
curr_last has to be updated accordingly
index of the alphabet symbol is stored in j
Transition is T[current_state_being scanned][j]
*/
// to get the current states number scan states[k]
temp_last = 0;
for (k = 0; k <= curr_last; k++) { //loop for scanning the transitions from every state in current
if (current[k] == "t")
continue;
for (x = 0; x < nos; x++)
if (states[x] == current[k])
break;
cnt = trans[x][j].cnt;
for (y = 0; y < cnt; y++){// iterating the list of transitions
str = trans[x][j].list[y];
flag = 0;
for (z = 0; z < temp_last; z++){ // checking whether the state is already present in the temp[]
if (str == "t") {
flag = 1;
break;
}
if (temp[z] == str) {
flag = 1;
break;
}
}
if (flag == 0)
temp[temp_last++] = str;
}
// updating the current and curr_last
}
for (y = 0; y <= temp_last; y++)
current[y] = temp[y];
curr_last = temp_last - 1; // as the last increment was not required
}
f = 0;
// loop checking for acceptance
for (i = 0; i <= curr_last; i++) {
for(j = 0; j < nofs; j++)
if (final[j] == current[i]) {
cout<<"\n----The string has been accepted----\n";
f = 1;
break;
}
if (f == 1) break;
}
if (f == 0)
cout<<"\n----The string has been rejected----\n";
}
return 0;
}
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.
- Check Automata Theory Books
- Practice Computer Science MCQs
- Check Computer Science Books
- Apply for Computer Science Internship