/**
* Finite Automata Demo.
*
* Defines the class Automaton, where:
* The states are unsigned ints (0, 1, ...);
* The initial state is 0;
* The alphabet includes all chars;
* Each state may have moves (transitions) associated with some chars;
* Undefined moves send the automaton to a "dead" state.
*
* Author: Erel Segal
* Created: 2010-12
*/
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
using namespace std;
typedef unsigned int State;
typedef map<char,State> Moves; // Moves === Transitions
class Automaton {
vector<Moves> myMoves; // myMoves[i] = moves from state i
unordered_set<State> myAcceptingStates;
protected:
bool run(const char* str, ostream* out=NULL) const {
State state = 0;
if (out) *out << '"' << str << '"' << ": ";
for (; *str; ++str) {
char c=*str;
if (out) *out << state << " -" << c << "-> ";
/* Move to next state */
const Moves* movesFromCurrentState = &myMoves[state];
Moves::const_iterator it = movesFromCurrentState->find(c);
if (it==movesFromCurrentState->end()) {
if (out) *out << "DEAD";
return false;
}
state = it->second;
}
if (myAcceptingStates.count(state)) {
if (out) *out << state << ": ACCEPT";
return true;
} else {
if (out) *out << state << ": REJECT";
return false;
}
}
public:
Automaton(int nStates): myMoves(nStates) {}
Automaton& addMove(State from, char c, State to) {
myMoves[from][c] = to;
return *this;
}
Automaton& addAccepting(State s) {
myAcceptingStates.insert(s);
return *this;
}
bool accepts(const char* s) const { return run(s,NULL); }
const Automaton& simulate(const char* s) const { run(s,&cout); cout<<endl; return *this; }
const Automaton& assert(const char* s, bool expected) const {
bool actual = run(s, NULL);
if (actual != expected) {
cerr << '"' << s << '"';
if (actual && !expected)
cerr << " should be rejected but was accepted:\n\t";
else
cerr << " should be accepted but was rejected:\n\t";
run(s, &cerr);
}
return *this;
}
}; // class Automaton
void testEven() {
Automaton evenAB(2);
cout << endl << "Detect even-length strings over {a,b}: "<<endl;
evenAB.addMove(0, 'a', 1).addMove(0, 'b', 1)
.addMove(1, 'a', 0).addMove(1, 'b', 0)
.addAccepting(0);
evenAB.assert("",true)
.assert("a",false).assert("b",false)
.assert("ab",true).assert("ba",true).assert("aa",true).assert("bb",true)
.assert("abba",true)
.assert("cc",false);
evenAB.simulate("")
.simulate("a")
.simulate("ab")
.simulate("bab")
.simulate("babbbbbb")
.simulate("babacaca")
;
}
void testPrefix() {
Automaton prefix(4);
cout << endl << "Detect strings that start with abc:"<<endl;
prefix.addMove(0,'a',1).addMove(1,'b',2).addMove(2,'c',3)
.addMove(3,'a',3).addMove(3,'b',3).addMove(3,'c',3)
.addAccepting(3);
prefix.assert("",false).assert("a",false).assert("ab",false).assert("abc",true)
.assert("abca",true).assert("abcb",true).assert("abcc",true).assert("abcba",true)
.assert("aabc",false).assert("babc",false).assert("cabc",false).assert("abcabc",true)
.assert("abb",false).assert("abbc",false);
prefix.simulate("ab")
.simulate("abc")
.simulate("abcabababcbc")
.simulate("abbabcabcabc")
;
}
void testSuffix() {
Automaton suffix(4);
cout << endl << "Detect strings that end with abc:"<<endl;
suffix.addMove(0,'a',1).addMove(1,'b',2).addMove(2,'c',3)
.addMove(0,'b',0).addMove(0,'c',0)
.addMove(1,'a',1).addMove(1,'c',0)
.addMove(2,'a',1).addMove(2,'b',0)
.addMove(3,'a',1).addMove(3,'b',0).addMove(3,'c',0)
.addAccepting(3);
suffix.assert("",false).assert("a",false).assert("ab",false).assert("abc",true)
.assert("abca",false).assert("abcb",false).assert("abcc",false).assert("abcba",false)
.assert("aabc",true).assert("babc",true).assert("cabc",true).assert("abcabc",true)
.assert("abb",false).assert("abbc",false);
suffix.simulate("ab")
.simulate("abc")
.simulate("bbbabababcbcabc")
.simulate("abcabcabcabb")
;
}
int main() {
testEven();
testPrefix();
testSuffix();
}
LyoqCiAqIEZpbml0ZSBBdXRvbWF0YSBEZW1vLgogKgogKiBEZWZpbmVzIHRoZSBjbGFzcyBBdXRvbWF0b24sIHdoZXJlOgogKiAgIFRoZSBzdGF0ZXMgYXJlIHVuc2lnbmVkIGludHMgKDAsIDEsIC4uLik7CiAqICAgVGhlIGluaXRpYWwgc3RhdGUgaXMgMDsKICogICBUaGUgYWxwaGFiZXQgaW5jbHVkZXMgYWxsIGNoYXJzOwogKiAgIEVhY2ggc3RhdGUgbWF5IGhhdmUgbW92ZXMgKHRyYW5zaXRpb25zKSBhc3NvY2lhdGVkIHdpdGggc29tZSBjaGFyczsKICogICAgICAgVW5kZWZpbmVkIG1vdmVzIHNlbmQgdGhlIGF1dG9tYXRvbiB0byBhICJkZWFkIiBzdGF0ZS4KICoKICogQXV0aG9yOiBFcmVsIFNlZ2FsCiAqIENyZWF0ZWQ6IDIwMTAtMTIKICovCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8bWFwPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiB1bnNpZ25lZCBpbnQgU3RhdGU7CnR5cGVkZWYgbWFwPGNoYXIsU3RhdGU+IE1vdmVzOyAvLyBNb3ZlcyA9PT0gVHJhbnNpdGlvbnMKCgpjbGFzcyBBdXRvbWF0b24gewoJdmVjdG9yPE1vdmVzPiBteU1vdmVzOyAvLyBteU1vdmVzW2ldID0gbW92ZXMgZnJvbSBzdGF0ZSBpCgl1bm9yZGVyZWRfc2V0PFN0YXRlPiBteUFjY2VwdGluZ1N0YXRlczsgCgkKcHJvdGVjdGVkOgoJCglib29sIHJ1bihjb25zdCBjaGFyKiBzdHIsIG9zdHJlYW0qIG91dD1OVUxMKSBjb25zdCB7CgkJU3RhdGUgc3RhdGUgPSAwOwoJCWlmIChvdXQpICpvdXQgPDwgJyInIDw8IHN0ciA8PCAnIicgPDwgIjogIjsKCQlmb3IgKDsgKnN0cjsgKytzdHIpIHsKCQkJY2hhciBjPSpzdHI7CgkJCWlmIChvdXQpICpvdXQgPDwgc3RhdGUgPDwgIiAtIiAgPDwgYyA8PCAiLT4gIjsKCgkJCS8qIE1vdmUgdG8gbmV4dCBzdGF0ZSAqLwoJCQljb25zdCBNb3ZlcyogbW92ZXNGcm9tQ3VycmVudFN0YXRlID0gJm15TW92ZXNbc3RhdGVdOwoJCQlNb3Zlczo6Y29uc3RfaXRlcmF0b3IgaXQgPSBtb3Zlc0Zyb21DdXJyZW50U3RhdGUtPmZpbmQoYyk7CgkJCWlmIChpdD09bW92ZXNGcm9tQ3VycmVudFN0YXRlLT5lbmQoKSkgewoJCQkJaWYgKG91dCkgKm91dCA8PCAiREVBRCI7CgkJCQlyZXR1cm4gZmFsc2U7CgkJCX0KCQkJc3RhdGUgPSBpdC0+c2Vjb25kOwoJCX0KCQlpZiAobXlBY2NlcHRpbmdTdGF0ZXMuY291bnQoc3RhdGUpKSB7CgkJCWlmIChvdXQpICpvdXQgPDwgc3RhdGUgPDwgIjogQUNDRVBUIjsKCQkJcmV0dXJuIHRydWU7CgkJfSBlbHNlIHsKCQkJaWYgKG91dCkgKm91dCA8PCBzdGF0ZSA8PCAiOiBSRUpFQ1QiOwoJCQlyZXR1cm4gZmFsc2U7CgkJfQoJfQoJCnB1YmxpYzoKCUF1dG9tYXRvbihpbnQgblN0YXRlcyk6IG15TW92ZXMoblN0YXRlcykge30KCglBdXRvbWF0b24mIGFkZE1vdmUoU3RhdGUgZnJvbSwgY2hhciBjLCBTdGF0ZSB0bykgewoJCW15TW92ZXNbZnJvbV1bY10gPSB0bzsKCQlyZXR1cm4gKnRoaXM7Cgl9CgkKCUF1dG9tYXRvbiYgYWRkQWNjZXB0aW5nKFN0YXRlIHMpIHsKCQlteUFjY2VwdGluZ1N0YXRlcy5pbnNlcnQocyk7CgkJcmV0dXJuICp0aGlzOwoJfQoKCWJvb2wgYWNjZXB0cyhjb25zdCBjaGFyKiBzKSBjb25zdCB7IHJldHVybiBydW4ocyxOVUxMKTsgfQoKCWNvbnN0IEF1dG9tYXRvbiYgc2ltdWxhdGUoY29uc3QgY2hhciogcykgY29uc3QgeyBydW4ocywmY291dCk7IGNvdXQ8PGVuZGw7IHJldHVybiAqdGhpczsgfQoJCgljb25zdCBBdXRvbWF0b24mIGFzc2VydChjb25zdCBjaGFyKiBzLCBib29sIGV4cGVjdGVkKSBjb25zdCB7CgkJYm9vbCBhY3R1YWwgPSBydW4ocywgTlVMTCk7CgkJaWYgKGFjdHVhbCAhPSBleHBlY3RlZCkgewoJCQljZXJyIDw8ICciJyA8PCBzIDw8ICciJzsKCQkJaWYgKGFjdHVhbCAmJiAhZXhwZWN0ZWQpCgkJCQljZXJyIDw8ICIgc2hvdWxkIGJlIHJlamVjdGVkIGJ1dCB3YXMgYWNjZXB0ZWQ6XG5cdCI7CgkJCWVsc2UKCQkJCWNlcnIgPDwgIiBzaG91bGQgYmUgYWNjZXB0ZWQgYnV0IHdhcyByZWplY3RlZDpcblx0IjsKCQkJcnVuKHMsICZjZXJyKTsKCQl9CgkJcmV0dXJuICp0aGlzOwoJfQp9OyAgLy8gY2xhc3MgQXV0b21hdG9uCgoKdm9pZCB0ZXN0RXZlbigpIHsKCUF1dG9tYXRvbiBldmVuQUIoMik7Cgljb3V0IDw8IGVuZGwgPDwgIkRldGVjdCBldmVuLWxlbmd0aCBzdHJpbmdzIG92ZXIge2EsYn06ICI8PGVuZGw7CglldmVuQUIuYWRkTW92ZSgwLCAnYScsIDEpLmFkZE1vdmUoMCwgJ2InLCAxKQoJICAgICAgLmFkZE1vdmUoMSwgJ2EnLCAwKS5hZGRNb3ZlKDEsICdiJywgMCkKCSAgICAgIC5hZGRBY2NlcHRpbmcoMCk7CglldmVuQUIuYXNzZXJ0KCIiLHRydWUpCgkgICAgICAuYXNzZXJ0KCJhIixmYWxzZSkuYXNzZXJ0KCJiIixmYWxzZSkKCSAgICAgIC5hc3NlcnQoImFiIix0cnVlKS5hc3NlcnQoImJhIix0cnVlKS5hc3NlcnQoImFhIix0cnVlKS5hc3NlcnQoImJiIix0cnVlKQoJICAgICAgLmFzc2VydCgiYWJiYSIsdHJ1ZSkKCSAgICAgIC5hc3NlcnQoImNjIixmYWxzZSk7CglldmVuQUIuc2ltdWxhdGUoIiIpCgkgICAgICAuc2ltdWxhdGUoImEiKQoJICAgICAgLnNpbXVsYXRlKCJhYiIpCgkgICAgICAuc2ltdWxhdGUoImJhYiIpCgkgICAgICAuc2ltdWxhdGUoImJhYmJiYmJiIikKCSAgICAgIC5zaW11bGF0ZSgiYmFiYWNhY2EiKQoJICAgICAgOwp9Cgp2b2lkIHRlc3RQcmVmaXgoKSB7CglBdXRvbWF0b24gcHJlZml4KDQpOwoJY291dCA8PCBlbmRsIDw8ICJEZXRlY3Qgc3RyaW5ncyB0aGF0IHN0YXJ0IHdpdGggYWJjOiI8PGVuZGw7CglwcmVmaXguYWRkTW92ZSgwLCdhJywxKS5hZGRNb3ZlKDEsJ2InLDIpLmFkZE1vdmUoMiwnYycsMykKCSAgICAgIC5hZGRNb3ZlKDMsJ2EnLDMpLmFkZE1vdmUoMywnYicsMykuYWRkTW92ZSgzLCdjJywzKQoJICAgICAgLmFkZEFjY2VwdGluZygzKTsKCXByZWZpeC5hc3NlcnQoIiIsZmFsc2UpLmFzc2VydCgiYSIsZmFsc2UpLmFzc2VydCgiYWIiLGZhbHNlKS5hc3NlcnQoImFiYyIsdHJ1ZSkKCSAgICAgIC5hc3NlcnQoImFiY2EiLHRydWUpLmFzc2VydCgiYWJjYiIsdHJ1ZSkuYXNzZXJ0KCJhYmNjIix0cnVlKS5hc3NlcnQoImFiY2JhIix0cnVlKQoJICAgICAgLmFzc2VydCgiYWFiYyIsZmFsc2UpLmFzc2VydCgiYmFiYyIsZmFsc2UpLmFzc2VydCgiY2FiYyIsZmFsc2UpLmFzc2VydCgiYWJjYWJjIix0cnVlKQoJICAgICAgLmFzc2VydCgiYWJiIixmYWxzZSkuYXNzZXJ0KCJhYmJjIixmYWxzZSk7CglwcmVmaXguc2ltdWxhdGUoImFiIikKCSAgICAgIC5zaW11bGF0ZSgiYWJjIikKCSAgICAgIC5zaW11bGF0ZSgiYWJjYWJhYmFiY2JjIikKCSAgICAgIC5zaW11bGF0ZSgiYWJiYWJjYWJjYWJjIikKCSAgICAgIDsKfQoKdm9pZCB0ZXN0U3VmZml4KCkgewoJQXV0b21hdG9uIHN1ZmZpeCg0KTsKCWNvdXQgPDwgZW5kbCA8PCAiRGV0ZWN0IHN0cmluZ3MgdGhhdCBlbmQgd2l0aCBhYmM6Ijw8ZW5kbDsKCXN1ZmZpeC5hZGRNb3ZlKDAsJ2EnLDEpLmFkZE1vdmUoMSwnYicsMikuYWRkTW92ZSgyLCdjJywzKQoJICAgICAgLmFkZE1vdmUoMCwnYicsMCkuYWRkTW92ZSgwLCdjJywwKQoJICAgICAgLmFkZE1vdmUoMSwnYScsMSkuYWRkTW92ZSgxLCdjJywwKQoJICAgICAgLmFkZE1vdmUoMiwnYScsMSkuYWRkTW92ZSgyLCdiJywwKQoJICAgICAgLmFkZE1vdmUoMywnYScsMSkuYWRkTW92ZSgzLCdiJywwKS5hZGRNb3ZlKDMsJ2MnLDApCgkgICAgICAuYWRkQWNjZXB0aW5nKDMpOwoJc3VmZml4LmFzc2VydCgiIixmYWxzZSkuYXNzZXJ0KCJhIixmYWxzZSkuYXNzZXJ0KCJhYiIsZmFsc2UpLmFzc2VydCgiYWJjIix0cnVlKQoJICAgICAgLmFzc2VydCgiYWJjYSIsZmFsc2UpLmFzc2VydCgiYWJjYiIsZmFsc2UpLmFzc2VydCgiYWJjYyIsZmFsc2UpLmFzc2VydCgiYWJjYmEiLGZhbHNlKQoJICAgICAgLmFzc2VydCgiYWFiYyIsdHJ1ZSkuYXNzZXJ0KCJiYWJjIix0cnVlKS5hc3NlcnQoImNhYmMiLHRydWUpLmFzc2VydCgiYWJjYWJjIix0cnVlKQoJICAgICAgLmFzc2VydCgiYWJiIixmYWxzZSkuYXNzZXJ0KCJhYmJjIixmYWxzZSk7CglzdWZmaXguc2ltdWxhdGUoImFiIikKCSAgICAgIC5zaW11bGF0ZSgiYWJjIikKCSAgICAgIC5zaW11bGF0ZSgiYmJiYWJhYmFiY2JjYWJjIikKCSAgICAgIC5zaW11bGF0ZSgiYWJjYWJjYWJjYWJiIikKCSAgICAgIDsKfQoKaW50IG1haW4oKSB7Cgl0ZXN0RXZlbigpOwoJdGVzdFByZWZpeCgpOwoJdGVzdFN1ZmZpeCgpOwp9CgoKCg==