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.

  1. #include <iostream>
  2. #include <string>
  3. #include <stdlib.h>
  4. #include <new>
  5. using namespace std;
  6.  
  7. int main() {
  8.     string *states, *final, *trap, **transition,input, tmp;
  9.     char *alf, temp;
  10.     int nos, nots, nofs, noa, i, j, current, flag;
  11.  
  12.     cout << "This is a program to simulate a DFA" << endl;
  13.     cout << "Enter the number of states, number of final states and"
  14.          << " the number of trap states.\n";
  15.     cin >> nos >> nofs >> nots;
  16.     cout << "Enter the number of symbols in the alphabet:\n";
  17.     cin >> noa;
  18.  
  19.     states = new string[nos];
  20.     final = new string[nofs];
  21.     trap = new string[nots];
  22.     alf = new char[noa+1];
  23.  
  24.     cout << "\nEnter the states (initial state first)\n";
  25.     for (i = 0; i < nos; i++)
  26.         cin >> states[i];
  27.  
  28.     cout << "Enter the final states:\n";
  29.     for (i = 0; i < nofs; i++)
  30.         cin >> final[i];
  31.  
  32.     cout << "Enter the trap states:\n";
  33.     for (i = 0; i < nots; i++)
  34.         cin >> trap[i];
  35.  
  36.     cout << "Enter the alphabet for the DFA:\n";
  37.     for (i = 0; i < noa; i++)
  38.         cin >> alf[i];
  39.  
  40.     //allocating space for the transition table
  41.     transition = new string *[nos];
  42.     for (i = 0; i < nos; i++)
  43.         transition[i] = new string[noa];
  44.  
  45.     //getting the values for the transition table    
  46.     cout << "Enter the transition for the given states:";
  47.     for (i = 0; i < nos; i++) {
  48.         cout << "\nFor state " << states[i] << endl;
  49.         for (j = 0; j < noa; j++) {
  50.             cout << "On input " << alf[j] << " to state : ";
  51.             cin >> transition[i][j];
  52.         }
  53.     }
  54.     cout << "The transition table you entered is :\n";
  55.     cout << "state\t";
  56.     for (i = 0; i < noa; i++)
  57.         cout << alf[i] << "\t";
  58.     for (i = 0; i < nos; i++) {
  59.         cout << endl << states[i] << "\t";
  60.         for (j = 0; j < noa; j++)
  61.             cout << transition[i][j] << "\t";
  62.     }
  63.  
  64.     while (true) {
  65.         current = 0, flag = 0;// current will keep track of the current state
  66.  
  67.         cout << "\nEnter the input string( enter exit to terminate) : ";
  68. 	cin >> input;
  69. 	if (input.compare("exit") == 0)
  70.             exit(0);
  71. 	for (i = 0; i < input.length(); i++) {
  72. 	    // process the string and change the state accordingly
  73.             temp = input.at(i);
  74. 	    // getting the index of the input from the alphabet set
  75. 	    for (j = 0; j < noa; j++) {
  76. 	        if (alf[j] == temp) {
  77. 	            break;
  78. 	        }
  79. 	    }
  80. 	    // storing the value of transition state
  81.             tmp = transition[current][j];
  82. 	    // changing the current state to the next state
  83. 	    for (int k = 0; k < nos; k++)
  84. 	        if (states[k].compare(tmp) == 0) {
  85. 	             current = k;
  86. 	             break;
  87. 	         }
  88. 	    // loop for checking if a the dfa is in a trap state
  89. 	    for (j = 0; j < nots; j++)
  90. 	        if (states[current].compare(trap[j]) == 0) {
  91. 	            cout << "The input string has been rejected";
  92.                     flag = 1;
  93. 	            break;
  94. 	        }
  95.  
  96.             if (flag == 1)
  97.                 break;
  98. 	}
  99.  
  100. 	    if (flag == 1)
  101.                 continue;
  102.  
  103. 	    for (i = 0; i < nofs; i++)
  104. 	        if (states[current].compare(final[i]) == 0) {
  105. 	            cout << "The input has been accepted by the DFA";
  106.                     flag = 1;
  107.                     break;
  108.                 }
  109.  
  110.             if (flag == 1)
  111.                 cout << "The input has been rejected by the DFA";
  112.     }
  113.     return 0;
  114. }

Output:

advertisement
advertisement

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.

Note: Join free Sanfoundry classes at Telegram or Youtube

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.