CplusplusCompiler/Simulation.cpp at master · adriano515/CplusplusCompiler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include "Simulation.h"
#include <array>
#include <algorithm>

using namespace std;

set<AutomataNode*> nodeSet; //global variable for the NFAset on e-closure of single nodes (is cleared on eClosure of sets)

set<AutomataNode*> nodeSet2;// global variable for the NFAset on e-closure for a set of NFAnodes (is cleared on eClosure of sets)

//set of NFA states reachable from NFA state s on epsilon-transitions alone
set<AutomataNode*> eClosure(AutomataNode* s){

    int i = s->getTransition().size();
    while(!i==0){
        if(s->getTransition()[i-1]->getValue()=='e'){
            eClosure(s->getTransition()[i-1]->getNextNode());
            }
        i = i -1;
    }

    nodeSet.insert(s);

    return nodeSet;

}

//set of NFA states reachable from NFA states s on epsilon-transitions alone
set<AutomataNode*> eClosure(set<AutomataNode*> s) {


    for (set<AutomataNode *>::iterator i = s.begin(); i != s.end(); i++) {
        AutomataNode *state = *i;
        nodeSet.clear();
        set<AutomataNode*> newSet= eClosure(state);

        for (set<AutomataNode *>::iterator it2 = newSet.begin(); it2 != newSet.end(); it2++) {
            AutomataNode *state2 = *it2;
            nodeSet2.insert(state2);
        }
    }

    set<AutomataNode*> nodeSet3 = nodeSet2; //Clearing global values so we can use the method again without having the previous values
    nodeSet2.clear();
    return nodeSet3;
}

//set of NFA states reachable from NFA states s on transition c
set<AutomataNode*> move(set<AutomataNode*> s, char c){
    set<AutomataNode*> nodeSet3;
    for (set<AutomataNode *>::iterator it2 = s.begin(); it2 != s.end(); it2++) {
        AutomataNode *state = *it2;
        for(int i=0;i<state->getTransition().size();i++){
            if(state->getTransition()[i]->getValue()==c){
                nodeSet3.insert(state->getTransition()[i]->getNextNode());
            }
        }
    }

    return nodeSet3;
}
bool nfaSimulation(string text,Automata* a) {
    set<AutomataNode*> final;
    final.insert(a->getFinNode());

    set<AutomataNode *> set2 = eClosure(a->getInitNode());
    set<AutomataNode *> set3;

    for (int i = 0; i < text.size(); i++) {
        set3 = move(set2, text[i]);
        set2 = eClosure(set3);
    }
    set<AutomataNode*> intersect;
    set_intersection(set2.begin(),set2.end(),final.begin(),final.end(),inserter(intersect,intersect.begin()));

    if (intersect.empty()){
        return false;
    }
    return true;
}


bool dfaSimulation(string text,AutomataDfa* a) {
    set<AutomataNode*> final;
    a->getFinNode().size();
    for (int i = 0; i<a->getFinNode().size();i++){
        final.insert(a->getFinNode()[i]);
    }

    set<AutomataNode *> set2 = eClosure(a->getInitNode());
    set<AutomataNode *> set3;

    for (int i = 0; i < text.size(); i++) {
        set3 = move(set2, text[i]);
        set2 = eClosure(set3);
    }
    set<AutomataNode*> intersect;
    set_intersection(set2.begin(),set2.end(),final.begin(),final.end(),inserter(intersect,intersect.begin()));

    if (intersect.empty()){
        return false;
    }
    return true;
}