NFA to DFA conversion


SUBMITTED BY: Guest

DATE: Nov. 12, 2013, 2:43 a.m.

FORMAT: Text only

SIZE: 6.6 kB

HITS: 787

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

comments powered by Disqus