NFA to DFA Conversion in C++

»
This is a C++ Program to convert NFA to DFA. A DFA (Deterministic Finite Automaton) is a finite state machine where from each state and a given input symbol, the next possible state is uniquely determined. On the other hand, an NFA (Non-Deterministic Finite Automaton) can move to several possible next states from a given state and a given input symbol. However, this does not add any more power to the machine. It still accepts the same set of languages, namely the regular languages. It is possible to convert an NFA to an equivalent DFA using the powerset construction.
The intuition behind this scheme is that an NFA can be in several possible states at any time. We can simulate it with a DFA whose states correspond to sets of states of the underlying NFA.

Here is source code of the C++ Program to Construct DFA from NFA. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <cstdio>
  2. #include <fstream>
  3. #include <iostream>
  4. #include <bitset>
  5. #include <vector>
  6. #include <cstring>
  7. #include <cstdlib>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <set>
  11. #define MAX_NFA_STATES 10
  12. #define MAX_ALPHABET_SIZE 10
  13. using namespace std;
  14. // Representation of an NFA state
  15. class NFAstate
  16. {
  17.     public:
  18.         int transitions[MAX_ALPHABET_SIZE][MAX_NFA_STATES];
  19.         NFAstate()
  20.         {
  21.             for (int i = 0; i < MAX_ALPHABET_SIZE; i++)
  22.                 for (int j = 0; j < MAX_NFA_STATES; j++)
  23.                     transitions[i][j] = -1;
  24.         }
  25. }*NFAstates;
  26. // Representation of a DFA state
  27. struct DFAstate
  28. {
  29.         bool finalState;
  30.         bitset<MAX_NFA_STATES> constituentNFAstates;
  31.         bitset<MAX_NFA_STATES> transitions[MAX_ALPHABET_SIZE];
  32.         int symbolicTransitions[MAX_ALPHABET_SIZE];
  33. };
  34. set<int> NFA_finalStates;
  35. vector<int> DFA_finalStates;
  36. vector<DFAstate*> DFAstates;
  37. queue<int> incompleteDFAstates;
  38. int N, M; // N -> No. of stattes, M -> Size of input alphabet
  39. // finds the epsilon closure of the NFA state "state" and stores it into "closure"
  40. void epsilonClosure(int state, bitset<MAX_NFA_STATES> &closure)
  41. {
  42.     for (int i = 0; i < N && NFAstates[state].transitions[0][i] != -1; i++)
  43.         if (closure[NFAstates[state].transitions[0][i]] == 0)
  44.         {
  45.             closure[NFAstates[state].transitions[0][i]] = 1;
  46.             epsilonClosure(NFAstates[state].transitions[0][i], closure);
  47.         }
  48. }
  49. // finds the epsilon closure of a set of NFA states "state" and stores it into "closure"
  50. void epsilonClosure(bitset<MAX_NFA_STATES> state,
  51.         bitset<MAX_NFA_STATES> &closure)
  52. {
  53.     for (int i = 0; i < N; i++)
  54.         if (state[i] == 1)
  55.             epsilonClosure(i, closure);
  56. }
  57. // returns a bitset representing the set of states the NFA could be in after moving
  58. // from state X on input symbol A
  59. void NFAmove(int X, int A, bitset<MAX_NFA_STATES> &Y)
  60. {
  61.     for (int i = 0; i < N && NFAstates[X].transitions[A][i] != -1; i++)
  62.         Y[NFAstates[X].transitions[A][i]] = 1;
  63. }
  64. // returns a bitset representing the set of states the NFA could be in after moving
  65. // from the set of states X on input symbol A
  66. void NFAmove(bitset<MAX_NFA_STATES> X, int A, bitset<MAX_NFA_STATES> &Y)
  67. {
  68.     for (int i = 0; i < N; i++)
  69.         if (X[i] == 1)
  70.             NFAmove(i, A, Y);
  71. }
  72. int main()
  73. {
  74.     int i, j, X, Y, A, T, F, D;
  75.     // read in the underlying NFA
  76.     ifstream fin("NFA.txt");
  77.     fin >> N >> M;
  78.     NFAstates = new NFAstate[N];
  79.     fin >> F;
  80.     for (i = 0; i < F; i++)
  81.     {
  82.         fin >> X;
  83.         NFA_finalStates.insert(X);
  84.     }
  85.     fin >> T;
  86.     while (T--)
  87.     {
  88.         fin >> X >> A >> Y;
  89.         for (i = 0; i < Y; i++)
  90.         {
  91.             fin >> j;
  92.             NFAstates[X].transitions[A][i] = j;
  93.         }
  94.     }
  95.     fin.close();
  96.     // construct the corresponding DFA
  97.     D = 1;
  98.     DFAstates.push_back(new DFAstate);
  99.     DFAstates[0]->constituentNFAstates[0] = 1;
  100.     epsilonClosure(0, DFAstates[0]->constituentNFAstates);
  101.     for (j = 0; j < N; j++)
  102.         if (DFAstates[0]->constituentNFAstates[j] == 1 && NFA_finalStates.find(
  103.                 j) != NFA_finalStates.end())
  104.         {
  105.             DFAstates[0]->finalState = true;
  106.             DFA_finalStates.push_back(0);
  107.             break;
  108.         }
  109.     incompleteDFAstates.push(0);
  110.     while (!incompleteDFAstates.empty())
  111.     {
  112.         X = incompleteDFAstates.front();
  113.         incompleteDFAstates.pop();
  114.         for (i = 1; i <= M; i++)
  115.         {
  116.             NFAmove(DFAstates[X]->constituentNFAstates, i,
  117.                     DFAstates[X]->transitions[i]);
  118.             epsilonClosure(DFAstates[X]->transitions[i],
  119.                     DFAstates[X]->transitions[i]);
  120.             for (j = 0; j < D; j++)
  121.                 if (DFAstates[X]->transitions[i]
  122.                         == DFAstates[j]->constituentNFAstates)
  123.                 {
  124.                     DFAstates[X]->symbolicTransitions[i] = j;
  125.                     break;
  126.                 }
  127.             if (j == D)
  128.             {
  129.                 DFAstates[X]->symbolicTransitions[i] = D;
  130.                 DFAstates.push_back(new DFAstate);
  131.                 DFAstates[D]->constituentNFAstates
  132.                         = DFAstates[X]->transitions[i];
  133.                 for (j = 0; j < N; j++)
  134.                     if (DFAstates[D]->constituentNFAstates[j] == 1
  135.                             && NFA_finalStates.find(j) != NFA_finalStates.end())
  136.                     {
  137.                         DFAstates[D]->finalState = true;
  138.                         DFA_finalStates.push_back(D);
  139.                         break;
  140.                     }
  141.                 incompleteDFAstates.push(D);
  142.                 D++;
  143.             }
  144.         }
  145.     }
  146.     // write out the corresponding DFA
  147.     ofstream fout("DFA.txt");
  148.     fout << D << " " << M << "\n" << DFA_finalStates.size();
  149.     for (vector<int>::iterator it = DFA_finalStates.begin(); it
  150.             != DFA_finalStates.end(); it++)
  151.         fout << " " << *it;
  152.     fout << "\n";
  153.     for (i = 0; i < D; i++)
  154.     {
  155.         for (j = 1; j <= M; j++)
  156.             fout << i << " " << j << " "
  157.                     << DFAstates[i]->symbolicTransitions[j] << "\n";
  158.     }
  159.     fout.close();
  160.     return 0;
  161. }

Output:

advertisement
$ g++ NFAtoDFA.cpp
$ a.out
 
Input file
NFA.txt
4 2
2 0 1
4
0 1 2 1 2
1 1 2 1 2
2 2 2 1 3
3 1 2 1 2
 
Output file
DFA.txt
4 2
3 0 1 3
0 1 1
0 2 2
1 1 1
1 2 3
2 1 2
2 2 2
3 1 1
3 2 2
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

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 & technical discussions at Telegram SanfoundryClasses.