Theory of Computation - Designing and Programming a DFA

Question: Design a DFA recognizing the given languages:
a) The language of all strings that do not end with 01.
b) The language of all strings that begin or end with 00 or 11.
c) The language of all strings containing no more than one occurrence of the string 00. (The string 000 should be viewed as containing two occurrence of 00.)
d) The language of all strings containing both 00 and 010 as substrings.
View Answer

Answer:
a) The language will contain the string that do not end with 01. That means the string 1001, 01, 01101, … should not be accepted by the DFA. So there will only be one non-accepting state and all the other states will be accepting states. The DFA for the given language can be represented by the following transition diagram :

b) The language will contain all the strings that either being or end with 00 or with 11. So the set of strings that will be accepted by the DFA is 11010, 001,1011, 10100, … The final states will the states in which we land when the beginning of the string is either 00 or 11 and the states in which we land when the end of the DFA is either 00 or 11. The DFA can be represented by the following transition diagram :

c) The set of string for the language that will be accepted by the DFA is 1001, 0100, 001,…. If at any stage we encounter three consecutive 0s or another pair of 0 the DFA will go into a trap state. Trap state is a state other than the final state from which transition to any other state is not possible. Hence the input is rejected by the DFA. The input will also be rejected if no pair of 0 is encountered. The DFA corresponding to the given language is represented by the transition graph given below:

d) The set of strings for the language is 110101, 1100101, 101011, … The string will be accepted by the DFA if both the sub-sequence 11 and 010 are present. Both 11 and 010 can follow each other in the language. So the DFA corresponding to the given language can be represented by the following transition diagram :

Question: Write a program to simulate a DFA. Test the program for any of the DFA given in the previous question.
Answer
A DFA can be simulated in various ways. One way is to store it as a transition table. The DFA tested in the output is the DFA for the third part of the previous question
Here is source code of the C++ Program to simulate deterministic finite automata. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <iostream>
```
```
#include <string>
```
```
#include <stdlib.h>
```
```
#include <new>
```
```
using namespace std;
```
```
 
```
```
int main() {
```

    string *states, *final, *trap, **transition,input, tmp;

```
    char *alf, temp;
```

    int nos, nots, nofs, noa, i, j, current, flag;

```
 
```

    cout << "This is a program to simulate a DFA" << endl;

    cout << "Enter the number of states, number of final states and"

         << " the number of trap states.\n";

```
    cin >> nos >> nofs >> nots;
```

    cout << "Enter the number of symbols in the alphabet:\n";

```
    cin >> noa;
```
```
 
```
```
    states = new string[nos];
```
```
    final = new string[nofs];
```
```
    trap = new string[nots];
```
```
    alf = new char[noa+1];
```
```
 
```

    cout << "\nEnter the states (initial 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 trap states:\n";
```
```
    for (i = 0; i < nots; i++)
```
```
        cin >> trap[i];
```
```
 
```

    cout << "Enter the alphabet for the DFA:\n";

```
    for (i = 0; i < noa; i++)
```
```
        cin >> alf[i];
```
```
 
```

    //allocating space for the transition table

```
    transition = new string *[nos];
```
```
    for (i = 0; i < nos; i++)
```

        transition[i] = new string[noa];

```
 
```

    //getting the values for the transition table

    cout << "Enter the transition for the given states:";

```
    for (i = 0; i < nos; i++) {
```

        cout << "\nFor state " << states[i] << endl;

```
        for (j = 0; j < noa; j++) {
```

            cout << "On input " << alf[j] << " to state : ";

```
            cin >> transition[i][j];
```
```
        }
```
```
    }
```

    cout << "The transition table you entered is :\n";

```
    cout << "state\t";
```
```
    for (i = 0; i < noa; i++)
```
```
        cout << alf[i] << "\t";
```
```
    for (i = 0; i < nos; i++) {
```

        cout << endl << states[i] << "\t";

```
        for (j = 0; j < noa; j++)
```

            cout << transition[i][j] << "\t";

```
    }
```
```
 
```
```
    while (true) {
```

        current = 0, flag = 0;// current will keep track of the current state

```
 
```

        cout << "\nEnter the input string( enter exit to terminate) : ";

```
	cin >> input;
```
```
	if (input.compare("exit") == 0)
```
```
            exit(0);
```
```
	for (i = 0; i < input.length(); i++) {
```

	    // process the string and change the state accordingly

```
            temp = input.at(i);
```

	    // getting the index of the input from the alphabet set

```
	    for (j = 0; j < noa; j++) {
```
```
	        if (alf[j] == temp) {
```
```
	            break;
```
```
	        }
```
```
	    }
```

	    // storing the value of transition state

            tmp = transition[current][j];

	    // changing the current state to the next state

```
	    for (int k = 0; k < nos; k++)
```

	        if (states[k].compare(tmp) == 0) {

```
	             current = k;
```
```
	             break;
```
```
	         }
```

	    // loop for checking if a the dfa is in a trap state

```
	    for (j = 0; j < nots; j++)
```

	        if (states[current].compare(trap[j]) == 0) {

	            cout << "The input string has been rejected";

```
                    flag = 1;
```
```
	            break;
```
```
	        }
```
```
 
```
```
            if (flag == 1)
```
```
                break;
```
```
	}
```
```
 
```
```
	    if (flag == 1)
```
```
                continue;
```
```
 
```
```
	    for (i = 0; i < nofs; i++)
```

	        if (states[current].compare(final[i]) == 0) {

	            cout << "The input has been accepted by the DFA";

```
                    flag = 1;
```
```
                    break;
```
```
                }
```
```
 
```
```
            if (flag == 1)
```

                cout << "The input has been rejected by the DFA";

```
    }
```
```
    return 0;
```
```
}
```

Output:

This is a program to simulate a DFA
Enter the number of states, number of final states and the number of trap states.
6
3
1
Enter the number of symbols in the alphabet:
2
 
Enter the states (initial state first)
q0
q1
q2
q3
q4
q5
Enter the final states:
q2
q3
q4
Enter the trap states:
q5
Enter the alphabet for the DFA:
0
1
Enter the transition for the given states:
For state q0
On input 0 to state : q1
On input 1 to state : q0
 
For state q1
On input 0 to state : q2
On input 1 to state : q0
 
For state q2
On input 0 to state : q5
On input 1 to state : q3
 
For state q3
On input 0 to state : q4
On input 1 to state : q3
 
For state q4
On input 0 to state : q5
On input 1 to state : q3
 
For state q5
On input 0 to state : q5
On input 1 to state : q5
The transition table you entered is :
state   0       1
q0      q1      q0
q1      q2      q0
q2      q5      q3
q3      q4      q3
q4      q5      q3
q5      q5      q5
Enter the input string( enter exit to terminate) : 11000110
The input string has been rejected
Enter the input string( enter exit to terminate) : 110010
The input has been accepted by the DFA
Enter the input string( enter exit to terminate) : 1100100
The input string has been rejected
Enter the input string( enter exit to terminate) : 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.

« Prev - Theory of Computation – Language of a DFA and Extended Transition Function

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

Recommended Articles: