fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define EPSILON char(222)
  4.  
  5. enum state_type{
  6. 	START, FINAL, INTERMEDIATE, START_AND_FINAL, DEAD, NONE
  7. };
  8.  
  9. struct edge{
  10. 	struct state * to;
  11. 	char input;
  12. 	edge(struct state * t, char i = EPSILON){
  13. 		to = t; input = i;
  14. 	}
  15. };
  16.  
  17. struct state{
  18. 	int id;
  19. 	state_type type;
  20. 	vector<edge *> edges;
  21. 	vector<state *> eps_closure;
  22. 	state(int &c, state_type t = INTERMEDIATE){
  23. 		id = c++;
  24. 		type = t;
  25. 	}
  26. 	state(){ }
  27. };
  28.  
  29. ostream & operator <<(ostream & out, edge * e){
  30. 	out<<"Edge: ";
  31. 	if(e->input == EPSILON)
  32. 		out<<"epsilon";
  33. 	else
  34. 		out<<e->input;
  35. 	out<<" -> "<<e->to->id<<endl;
  36. 	return out;
  37. }
  38.  
  39. ostream & operator <<(ostream & out, state * s){
  40. 	out<<"State: "<<s->id<<endl;
  41. 	out<<"Type: ";
  42. 	switch(s->type){
  43. 		case 0: out<<"START";
  44. 				break;
  45. 		case 1: out<<"FINAL";
  46. 				break;
  47. 		case 2: out<<"INTERMEDIATE";
  48. 				break;
  49. 		case 3: out<<"START_AND_FINAL";
  50. 				break;
  51. 		case 4: out<<"DEAD";
  52. 				break;
  53. 		case 5: out<<"NONE";
  54. 				break;
  55. 	}
  56. 	out<<endl;
  57. 	for(int i=0; i<s->edges.size(); i++){
  58. 		out<<s->edges[i];
  59. 	}
  60. 	return out;
  61. }
  62.  
  63. struct state_set{
  64. 	state *start, *end;
  65. 	state_set(int &counter){ start = new state(counter); end = new state(counter); }
  66. 	state_set(state *s, state *e){ start = s; end = e; }
  67. };
  68.  
  69. class NFA{
  70. 	int counter = 0;
  71. 	vector<state *> states;
  72.  
  73. 	public:
  74.  
  75. 	NFA(string s){
  76. 		cout<<"Initializing NFA: "<<s<<endl;
  77. 		state_set * ss = concat(
  78. 			OR(
  79. 				transition('a'),
  80. 				transition('b')
  81. 			),
  82. 			concat(
  83. 				transition('a'),
  84. 				concat(
  85. 					transition('b'),
  86. 					transition('b')
  87. 				)
  88. 			)
  89. 		);
  90. 		ss->start->type = START;
  91. 		ss->end->type = FINAL;
  92. 	}
  93. 	void print(bool closure = false){
  94. 		cout<<"Printing NFA\n"<<endl;
  95. 		for(int i=0; i<states.size(); i++){
  96. 			cout<<states[i];
  97. 			if(closure){
  98. 				cout<<"Epsilon closure: ";
  99. 				for(int j=0; j<states[i]->eps_closure.size(); j++)
  100. 					cout<<states[i]->eps_closure[j]->id<<" ";
  101. 			}
  102. 			cout<<endl<<endl;
  103. 		}
  104. 	}
  105. 	void insert_states(state_set * ss){
  106. 		states.push_back(ss->start);
  107. 		states.push_back(ss->end);
  108. 		return;
  109. 	}
  110. 	state_set * transition(char input){
  111. 		state_set * ss = new state_set(counter);
  112. 		ss->start->edges.push_back(new edge(ss->end, input));
  113. 		insert_states(ss);
  114. 		return ss;
  115. 	}
  116. 	state_set * star(state_set * input_ss){
  117. 		state_set * ss = new state_set(counter);
  118. 		ss->start->edges.push_back(new edge(input_ss->start));
  119. 		ss->start->edges.push_back(new edge(ss->end));
  120. 		input_ss->end->edges.push_back(new edge(ss->end));
  121. 		input_ss->end->edges.push_back(new edge(input_ss->start));
  122. 		insert_states(ss);
  123. 		return ss;
  124. 	}
  125. 	state_set * concat(state_set * ss1, state_set * ss2){
  126. 		ss1->end->edges.push_back(new edge(ss2->start));
  127. 		return new state_set(ss1->start, ss2->end);
  128. 	}
  129. 	state_set * OR(state_set * ss1, state_set * ss2){
  130. 		state_set * ss = new state_set(counter);
  131. 		ss->start->edges.push_back(new edge(ss1->start));
  132. 		ss->start->edges.push_back(new edge(ss2->start));
  133. 		ss1->end->edges.push_back(new edge(ss->end));
  134. 		ss2->end->edges.push_back(new edge(ss->end));
  135. 		insert_states(ss);
  136. 		return ss;
  137. 	}
  138. 	void get_closures(){
  139. 		for(int i=0; i<states.size(); i++){
  140. 			for(int j=0; j<states[i]->edges.size(); j++){
  141. 				states[i]->eps_closure.push_back(states[i]);
  142. 				if(states[i]->edges[j]->input == EPSILON){
  143. 					states[i]->eps_closure.push_back(states[i]->edges[j]->to);
  144. 				}
  145. 			}
  146. 		}
  147. 		bool change = true;
  148. 		while(change){
  149. 			change = false;
  150. 			for(int i=0; i<states.size(); i++){
  151. 				for(int j=0; j<states[i]->eps_closure.size(); j++){
  152. 					for(int k=0; k<states[i]->eps_closure[j]->eps_closure.size(); k++){
  153. 						if(find(states[i]->eps_closure.begin(), states[i]->eps_closure.end(), states[i]->eps_closure[j]->eps_closure[k]) == states[i]->eps_closure.end()){
  154. 							states[i]->eps_closure.push_back(states[i]->eps_closure[j]->eps_closure[k]);
  155. 							change = true;
  156. 						}
  157. 					}
  158. 				}
  159. 			}
  160. 		}
  161. 	}
  162. };
  163.  
  164. int main() {
  165. 	string s;
  166. 	s = "(a/b)*abb";
  167. 	// cin>>s;
  168. 	NFA nfa(s);
  169. 	// nfa.print();
  170. 	nfa.get_closures();
  171. 	nfa.print(true);
  172. 	return 0;
  173. }
  174.  
Success #stdin #stdout 0s 4356KB
comments (?)
stdin
copy 
aab*
stdout
copy 
Initializing NFA: (a/b)*abb
Printing NFA

State: 0
Type: INTERMEDIATE
Edge: b -> 1
Epsilon closure: 0 

State: 1
Type: FINAL
Epsilon closure: 

State: 2
Type: INTERMEDIATE
Edge: b -> 3
Epsilon closure: 2 

State: 3
Type: INTERMEDIATE
Edge: epsilon -> 0
Epsilon closure: 3 0 

State: 4
Type: INTERMEDIATE
Edge: a -> 5
Epsilon closure: 4 

State: 5
Type: INTERMEDIATE
Edge: epsilon -> 2
Epsilon closure: 5 2 

State: 6
Type: INTERMEDIATE
Edge: b -> 7
Epsilon closure: 6 

State: 7
Type: INTERMEDIATE
Edge: epsilon -> 11
Epsilon closure: 7 11 4 

State: 8
Type: INTERMEDIATE
Edge: a -> 9
Epsilon closure: 8 

State: 9
Type: INTERMEDIATE
Edge: epsilon -> 11
Epsilon closure: 9 11 4 

State: 10
Type: START
Edge: epsilon -> 8
Edge: epsilon -> 6
Epsilon closure: 10 8 10 6 

State: 11
Type: INTERMEDIATE
Edge: epsilon -> 4
Epsilon closure: 11 4
https://ideone.com/L0Y7Qz
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!