TeoriaComputacionProyecto/main.cpp at main · jneirar/TeoriaComputacionProyecto · 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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include "lib.h"
#include "functions.h"

bool flag = 0;
unsigned t0, t1;
double tiempo;

void solve();
void generateAFD(ll opt2, ll &n, ll &qi, ll &nqf, unordered_set<ll> &qf, vector<vector<ll>> &transition);
double timeCalculate(double t0, double t1);

int main(){
    srand (time(NULL));
    do{
        flag = 0;
        solve();
    }while(flag);
    cout << "\n\nPrograma finalizado exitosamente\n\n";
    return 0;
}

void solve(){
    int opt1 = menu1();
    if(opt1 == 4)
        return;
    int opt2 = menu2();
    if(opt2 == 4){
        flag = 1;
        return;
    }
    if(opt2 == 5)
        return;

    ll n, qi, nqf;
    unordered_set<ll> qf;
    vector<vector<ll>> transition;

    switch (opt1){
        case 1:{    //Algoritmo MinSinc
            while(1){
                generateAFD(opt2, n, qi, nqf, qf, transition);
                //Automata leido
                t0 = clock();
                string minCad = Min_Sinc(transition, n);
                t1 = clock();
                if(minCad == ".")   cout << "\nNO\n";
                else    cout << "\nMin-Sinc: " << minCad << "\nTamanio: " << minCad.length() << "\n";
                tiempo = timeCalculate(t0, t1);
                cout << "\nExecution Time: " << tiempo << "\n";

                string flag2;
                cout << "\n\nProbar Min-Sinc en otro AFD (S/N): ";
                cin >> flag2;
                if(flag2 == "N" || flag2 == "n")
                    break;
            }
            break;
        }
        case 2:{    //Algoritmo Dec-Sinc
            while(1){
                generateAFD(opt2, n, qi, nqf, qf, transition);
                //Automata leído
                t0 = clock();
                if(Dec_Sinc(n, transition))   cout << "SI\n";
                else cout << "NO\n";
                t1 = clock();
                tiempo = timeCalculate(t0, t1);
                cout << "\nExecution Time: " << tiempo << "\n";

                string flag2;
                cout << "\n\nProbar Dec-Sinc en otro AFD (S/N): ";
                cin >> flag2;
                if(flag2 == "N" || flag2 == "n")
                    break;
            }
            break;
        }
        case 3:{    //Algoritmo Cad-Sinc
            while(1){
                generateAFD(opt2, n, qi, nqf, qf, transition);
                //Automata leído
                if(!Dec_Sinc(n, transition))
                    cout << "\nNo es sincronizable\n";
                else{
                    t0 = clock();
                    string cadSinc = Cad_Sinc(n, transition);
                    t1 = clock();
                    cout << "\nCadena: " << cadSinc << "\n";
                    cout << "Tamanio: " << cadSinc.length() << "\n";
                    tiempo = timeCalculate(t0, t1);
                    cout << "\nExecution Time: " << tiempo << "\n";
                }

                string flag2;
                cout << "\n\nProbar Cad-Sinc en otro AFD (S/N): ";
                cin >> flag2;
                if(flag2 == "N" || flag2 == "n")
                    break;
            }
            break;
        }
    }
    string flag1;
    cout << "\n\nProbar otro problema (S/N): ";
    cin >> flag1;
    if(flag1 != "N" && flag1 != "n")
        flag = 1;
}

void generateAFD(ll opt2, ll &n, ll &qi, ll &nqf, unordered_set<ll> &qf, vector<vector<ll>> &transition){
    switch (opt2){
        case 1:{    //Lee de consola
            cout << "\nInserta el automata en el formato indicado.\n";
            cin >> n >> qi >> nqf;
            ll tmp1, tmp2;
            for(ll i=0; i<nqf; i++){
                cin >> tmp1;
                qf.insert(tmp1);
            }
            transition.resize(n);
            for(ll i=0; i<n; i++)   transition[i].resize(2);
            for(ll i=0; i<2*n; i++)
                cin >> tmp1 >> tmp2 >> transition[tmp1][tmp2];
            break;
        }
        case 2:{//Aleatorio
            qi = 0;
            nqf = 1;
            qf.insert(1);
            do{
                cout << "\nInserta el tamanio del automata: ";
                cin >> n;
            }while(n < 2);
            transition.resize(n);
            for(ll i=0; i<n; i++)   transition[i].resize(2);
            for(ll i=0; i<n; i++){
                transition[i][0] = rand() % n;
                transition[i][1] = rand() % n;
            }
            cout << "\nAutomata generado: \n";
            cout << n << " 0 1 1\n";
            for(ll i=0; i<n; i++){
                cout << i << " 0 " << transition[i][0] << "\n";
                cout << i << " 1 " << transition[i][1] << "\n";
            }
            break;
        }
        case 3:{//Aleatorio Sinc Cerny
            qi = 0;
            nqf = 1;
            qf.insert(1);
            do{
                cout << "\nInserta el tamanio del automata de Cerny: ";
                cin >> n;
            }while(n < 2);
            transition.resize(n);
            for(ll i=0; i<n; i++)   transition[i].resize(2);
            transition[0][0] = 1;
            transition[0][1] = 1;
            for(ll i=1; i<n; i++){
                transition[i][0] = i;
                transition[i][1] = (i+1)%n;
            }
            cout << "\n\tAutomata de Cerny generado: \n";
            cout << n << " 0 1 1\n";
            for(ll i=0; i<n; i++){
                cout << i << " 0 " << transition[i][0] << "\n";
                cout << i << " 1 " << transition[i][1] << "\n";
            }
            break;
        }
    }
}

double timeCalculate(double t0, double t1){
    return (double(t1-t0)/(CLOCKS_PER_SEC/1));
}