fork(3) download
copy 
  1. /**
  2.  * Finite Automata Demo.
  3.  *
  4.  * Defines the class Automaton, where:
  5.  *   The states are unsigned ints (0, 1, ...);
  6.  *   The initial state is 0;
  7.  *   The alphabet includes all chars;
  8.  *   Each state may have moves (transitions) associated with some chars;
  9.  *       Undefined moves send the automaton to a "dead" state.
  10.  *
  11.  * Author: Erel Segal
  12.  * Created: 2010-12
  13.  */
  14.  
  15. #include <iostream>
  16. #include <vector>
  17. #include <set>
  18. #include <unordered_set>
  19. #include <map>
  20. using namespace std;
  21.  
  22. typedef unsigned int State;
  23. typedef map<char,State> Moves; // Moves === Transitions
  24.  
  25.  
  26. class Automaton {
  27. 	vector<Moves> myMoves; // myMoves[i] = moves from state i
  28. 	unordered_set<State> myAcceptingStates; 
  29.  
  30. protected:
  31.  
  32. 	bool run(const char* str, ostream* out=NULL) const {
  33. 		State state = 0;
  34. 		if (out) *out << '"' << str << '"' << ": ";
  35. 		for (; *str; ++str) {
  36. 			char c=*str;
  37. 			if (out) *out << state << " -"  << c << "-> ";
  38.  
  39. 			/* Move to next state */
  40. 			const Moves* movesFromCurrentState = &myMoves[state];
  41. 			Moves::const_iterator it = movesFromCurrentState->find(c);
  42. 			if (it==movesFromCurrentState->end()) {
  43. 				if (out) *out << "DEAD";
  44. 				return false;
  45. 			}
  46. 			state = it->second;
  47. 		}
  48. 		if (myAcceptingStates.count(state)) {
  49. 			if (out) *out << state << ": ACCEPT";
  50. 			return true;
  51. 		} else {
  52. 			if (out) *out << state << ": REJECT";
  53. 			return false;
  54. 		}
  55. 	}
  56.  
  57. public:
  58. 	Automaton(int nStates): myMoves(nStates) {}
  59.  
  60. 	Automaton& addMove(State from, char c, State to) {
  61. 		myMoves[from][c] = to;
  62. 		return *this;
  63. 	}
  64.  
  65. 	Automaton& addAccepting(State s) {
  66. 		myAcceptingStates.insert(s);
  67. 		return *this;
  68. 	}
  69.  
  70. 	bool accepts(const char* s) const { return run(s,NULL); }
  71.  
  72. 	const Automaton& simulate(const char* s) const { run(s,&cout); cout<<endl; return *this; }
  73.  
  74. 	const Automaton& assert(const char* s, bool expected) const {
  75. 		bool actual = run(s, NULL);
  76. 		if (actual != expected) {
  77. 			cerr << '"' << s << '"';
  78. 			if (actual && !expected)
  79. 				cerr << " should be rejected but was accepted:\n\t";
  80. 			else
  81. 				cerr << " should be accepted but was rejected:\n\t";
  82. 			run(s, &cerr);
  83. 		}
  84. 		return *this;
  85. 	}
  86. };  // class Automaton
  87.  
  88.  
  89. void testEven() {
  90. 	Automaton evenAB(2);
  91. 	cout << endl << "Detect even-length strings over {a,b}: "<<endl;
  92. 	evenAB.addMove(0, 'a', 1).addMove(0, 'b', 1)
  93. 	      .addMove(1, 'a', 0).addMove(1, 'b', 0)
  94. 	      .addAccepting(0);
  95. 	evenAB.assert("",true)
  96. 	      .assert("a",false).assert("b",false)
  97. 	      .assert("ab",true).assert("ba",true).assert("aa",true).assert("bb",true)
  98. 	      .assert("abba",true)
  99. 	      .assert("cc",false);
  100. 	evenAB.simulate("")
  101. 	      .simulate("a")
  102. 	      .simulate("ab")
  103. 	      .simulate("bab")
  104. 	      .simulate("babbbbbb")
  105. 	      .simulate("babacaca")
  106. 	      ;
  107. }
  108.  
  109. void testPrefix() {
  110. 	Automaton prefix(4);
  111. 	cout << endl << "Detect strings that start with abc:"<<endl;
  112. 	prefix.addMove(0,'a',1).addMove(1,'b',2).addMove(2,'c',3)
  113. 	      .addMove(3,'a',3).addMove(3,'b',3).addMove(3,'c',3)
  114. 	      .addAccepting(3);
  115. 	prefix.assert("",false).assert("a",false).assert("ab",false).assert("abc",true)
  116. 	      .assert("abca",true).assert("abcb",true).assert("abcc",true).assert("abcba",true)
  117. 	      .assert("aabc",false).assert("babc",false).assert("cabc",false).assert("abcabc",true)
  118. 	      .assert("abb",false).assert("abbc",false);
  119. 	prefix.simulate("ab")
  120. 	      .simulate("abc")
  121. 	      .simulate("abcabababcbc")
  122. 	      .simulate("abbabcabcabc")
  123. 	      ;
  124. }
  125.  
  126. void testSuffix() {
  127. 	Automaton suffix(4);
  128. 	cout << endl << "Detect strings that end with abc:"<<endl;
  129. 	suffix.addMove(0,'a',1).addMove(1,'b',2).addMove(2,'c',3)
  130. 	      .addMove(0,'b',0).addMove(0,'c',0)
  131. 	      .addMove(1,'a',1).addMove(1,'c',0)
  132. 	      .addMove(2,'a',1).addMove(2,'b',0)
  133. 	      .addMove(3,'a',1).addMove(3,'b',0).addMove(3,'c',0)
  134. 	      .addAccepting(3);
  135. 	suffix.assert("",false).assert("a",false).assert("ab",false).assert("abc",true)
  136. 	      .assert("abca",false).assert("abcb",false).assert("abcc",false).assert("abcba",false)
  137. 	      .assert("aabc",true).assert("babc",true).assert("cabc",true).assert("abcabc",true)
  138. 	      .assert("abb",false).assert("abbc",false);
  139. 	suffix.simulate("ab")
  140. 	      .simulate("abc")
  141. 	      .simulate("bbbabababcbcabc")
  142. 	      .simulate("abcabcabcabb")
  143. 	      ;
  144. }
  145.  
  146. int main() {
  147. 	testEven();
  148. 	testPrefix();
  149. 	testSuffix();
  150. }
  151.  
  152.  
  153.  
  154.  
Success #stdin #stdout 0s 2988KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Detect even-length strings over {a,b}: 
"": 0: ACCEPT
"a": 0 -a-> 1: REJECT
"ab": 0 -a-> 1 -b-> 0: ACCEPT
"bab": 0 -b-> 1 -a-> 0 -b-> 1: REJECT
"babbbbbb": 0 -b-> 1 -a-> 0 -b-> 1 -b-> 0 -b-> 1 -b-> 0 -b-> 1 -b-> 0: ACCEPT
"babacaca": 0 -b-> 1 -a-> 0 -b-> 1 -a-> 0 -c-> DEAD

Detect strings that start with abc:
"ab": 0 -a-> 1 -b-> 2: REJECT
"abc": 0 -a-> 1 -b-> 2 -c-> 3: ACCEPT
"abcabababcbc": 0 -a-> 1 -b-> 2 -c-> 3 -a-> 3 -b-> 3 -a-> 3 -b-> 3 -a-> 3 -b-> 3 -c-> 3 -b-> 3 -c-> 3: ACCEPT
"abbabcabcabc": 0 -a-> 1 -b-> 2 -b-> DEAD

Detect strings that end with abc:
"ab": 0 -a-> 1 -b-> 2: REJECT
"abc": 0 -a-> 1 -b-> 2 -c-> 3: ACCEPT
"bbbabababcbcabc": 0 -b-> 0 -b-> 0 -b-> 0 -a-> 1 -b-> 2 -a-> 1 -b-> 2 -a-> 1 -b-> 2 -c-> 3 -b-> 0 -c-> 0 -a-> 1 -b-> 2 -c-> 3: ACCEPT
"abcabcabcabb": 0 -a-> 1 -b-> 2 -c-> 3 -a-> 1 -b-> 2 -c-> 3 -a-> 1 -b-> 2 -c-> 3 -a-> 1 -b-> 2 -b-> 0: REJECT
https://ideone.com/MksaL
language:
C++14 (gcc 8.3)
created:
13 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!